The following context-free grammar (CFG) has unit productions. S ? aXZa | aXa |

Question

The following context-free grammar (CFG) has unit productions.

S ? aXZa | aXa | aZa |aa

X ? Y | a

Y ? Z | b

Z ? bZ | b

Using the algorithm presented in chapter 13, find a CFG for the same language that does not have any unit productions.

b) Convert the grammar you obtained as a result of part (a) into Chomsky Normal Form (CNF).

Q6)a) The following context-free grammar (CFG) has unit productions. 5 Points Using the algorithm presented in chapter 13, find a CFG for the same language that does not have any unit productions. b) Convert the grammar you obtained as a result of part (a) into Chomsky Normal Form (CNF) 5 Points

Explanation / Answer

Here we have the CFG:

S ->aXZa | aXa | aZa |aa

X -> Y | a

Y -> Z | b

Z -> bZ | b

Such that X -> Y and Y -> Z are the two unit productions in the CFG.
For the productions Y-> Z we have Z->bZ|b , so we will add Z->bZ|b to the grammar and then remove Y->Z from the grammar. Now for the other production X->Y, we have production Y->bZ|b |bso we add X->bZ|b|b|a to the grammar. So the grammar after removal of unit production is

S ->aXZa | aXa | aZa |aa

X -> bZ| b| b| a

Y -> bZ| b| b

Z -> bZ | b

removing repeated productions:

S ->aXZa | aXa | aZa |aa

X -> bZ | b | a

Y -> bZ | b

Z -> bZ | b

b).Converting to CNF:

S ->aXZa | aXa | aZa |aa

X -> bZ | b | a

Y -> bZ | b

Z -> bZ | b

Step-1:Eliminate start symbol from RHS

S0->S

S ->aXZa | aXa | aZa |aa

X -> bZ | b | a

Y -> bZ | b

Z -> bZ | b

step-2:Removing and replacing terminals:
S0->S

S ->aXZa | aXa | aZa |aa

X -> bZ | b | a

Y -> bZ | b

Z -> bZ | b

W->a

V->b

then,

S0->WXZW | WXW | WZW | WW | S

S ->WXZW | WXW | WZW | WW

X -> VZ | b | a

Y -> VZ | b

Z -> VZ | b

W->a

V->b

then we have more than 3 non-terminals in each of the production:

S0->LW | RW | UW | WW | S

S ->LW | RW | UW | WW

X -> VZ | V | a

Y -> VZ | b

Z -> VZ | b

W->a

V->b

R->WX

U->WZ

L->RZ

This is the final CNF.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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