convert the context-free grammar G = , where into a Chomsky normal form grammar

Question

convert the context-free grammar G = , where

into a Chomsky normal form grammar G' = . At each stage, your answers should show the steps of the conversion, namely which rules are being removed and what rules are being added, if any.

A) Rewrite the productions of G as a list of individual productions rather than in the disjunctive notation used above, and for each of these productions, indicate whether it is of one of the forms allowed in Chomsky normal form.

B) State the new production added to the list to take account of the new start variable S' .

C) dentify any unallowed productions and list the productions added to replace these unallowed productions. Repeat these steps for any new unallowed productions added.

D) Identify and eliminate any unit productions, along with any new unit productions added in eliminating these.

E) Remove the remaining productions that are not in Chomsky normal form, and indicate the productions added to replace each removed production. Reuse variables introduced for terminal symbols. You may also reuse sequencing variables when removed productions have the same right hand sides.

Explanation / Answer

Context free Grammer is in the Chomsky Normal Form If the productions are in the following forms:

A -> BC

A -> a

S -> epsilon ,where S is strat symbol.

Writing the productions individualy:

S -> 0S0 It' s not in the chomsky normal form

S -> A It' s not in the chomsky normal form

A -> 1A1    It' s not in the chomsky normal form

A -> epsilon It' s not in the chomsky normal form

A -> 0S It' s not in the chomsky normal form

S is in the right hand side of the products ,Add a new state S0 ,S0 -> S is added to the productions and productions are:

S0 -> S

S -> 0S0

S -> A

A -> 1A1

A -> epsilon

A -> 0S

Now Remove the Null Production, A -> epsilon,

After Removing Null production ,Production set becomes:

S0 -> S

S -> 0S0

S -> A

S -> epsilon

A -> 1A1

A -> 11

A -> 0S

Now Remove the Null Production S -> epsilon,

After Removing Null production ,Production set becomes:

S0 -> S

S0 -> epsilon

S -> 0S0

S -> A

S -> 00

A -> 1A1

A -> 11

A -> 0S

A -> 0

S0 -> epsilon can not be removed because it is in tn the CNF ,S0 is start symbol.

Now we will remove the unit productions.

Removing unit product S -> A So production sets:

S0 -> S | epsilon

S -> 0S0 | 00 | 1A1 | 0 | 11 | 0S

A -> 1A1 | 0 | 11 | 0S

Removing unit production S0 -> S,and Production sets are:

S0 -> 0S0 | 00 | 1A1 | 0 | 11 | 0S | epsilon

S -> 0S0 | 00 | 1A1 | 0 | 11 | 0S

A -> 1A1 | 0 | 11 | 0S

Now 2 teminal values are not allowed in CNF so add B -> 0 and C -> 1

Now production sets:

S0 -> BSB | BB | CAC | 0 | CC | BS | epsilon

S -> BSB | BB | CAC | 0 | CC | BS

A -> CAC | 0 | CC | BS

B -> 0

C -> 1

Now find out more than two variables in the R.H.S of products:

S0 -> BSB, S0 - > CAC, S -> BSB ,S -> CAC , A -> CAC

So the rule S0 BSB is replaced by the 2 rules S0 BA1 and A1 SB. Also the rule S BSB is replaced by the 2 rules S BA2 and A2 SB and S0 -> CAC is replaced by S0 -> CB1 and B1 -> AC ,

S -> CAC is replaced by S -> CB2 and B2 -> AC ,and A -> CAC is replaced by A -> CB3 and B3 -> AC ,

S0 -> BA1 | BB | CB1 | 0 | CC | BS | epsilon

S -> BA2 | BB | CB2 | 0 | CC | BS

A -> CB3 | 0 | CC | BS

B -> 0

C -> 1

A1 -> SB

A2 -> SB

B1 -> AC

B2 -> AC

B3 -> AC

So the grammer is in CNF.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.