- Find a CFG for the same language that does not have any unit productions. - Co
ID: 3801889 • Letter: #
Question
- Find a CFG for the same language that does not have any unit productions.
- Convert the grammar you obtained as a result of part (a) into Chomsky Normal Form (CNF).
2. The following context-free grammar (CFG) has unit productions. aa,Explanation / Answer
S - > aXZa S -> aXa S -> aZa S -> aa X -> Y X -> a Y -> Z Y -> b Z -> bZ Z ->b There are 2 unit productions X -> Y Y -> Z Y -> Z and Z -> bZ/b we can write Y -> bZ/b and remove Y -> Z Revised production: S - > aXZa S -> aXa S -> aZa S -> aa X -> Y X -> a Y -> bZ Y -> b Z -> bZ Z ->b X -> Y and Y-> bZ/b we can write X -> bZ/b Revised production: S - > aXZa S -> aXa S -> aZa S -> aa X -> bZ X -> b X -> a Y -> bZ Y -> b Z -> bZ Z ->b From above Productions rules 8 and 9 are unused. We can eliminate them Revised production: S - > aXZa / aXa / aZa / aa X -> bZ / b /a Z -> bZ / b CNF: Revised production: S - > C3C4 / C3C1 / C1C4 / C1C1 X -> C2Z / b /a Z -> C2Z / b C3 -> C1X C4 -> ZC1 C1 -> a C2 -> b
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.