Consider the following grammar:S - aBAA -aAE | EB -bBC | bC - cCD | DD -aDCE -ED | eE | eF - SeFAfter removal of useless symbols, how many productions violate the rules ofgreibach normal form?Correct answer is '1'. Can you explain this answer?

Question

Answer

Identifying the Violation of Greibach Normal Form

To determine the number of productions that violate the rules of Greibach Normal Form in the given grammar after removal of useless symbols, we need to consider the following rules of Greibach Normal Form:
1. Each production should have a single non-terminal as the leftmost symbol.
2. Each production should have a terminal as the second symbol.
3. Each production should have a string of terminals and non-terminals following the second symbol.

Analysis of the given grammar

After removing useless symbols, the grammar becomes:
S -> aB
A -> aAE | E
B -> bBC
C -> cCD
D -> aD
E -> eE | eF
F -> SeF

Evaluating the productions

1. S -> aB (violates GNF rule as 'a' is a terminal but not the second symbol)
2. A -> aAE | E (satisfies GNF rules)
3. B -> bBC (satisfies GNF rules)
4. C -> cCD (satisfies GNF rules)
5. D -> aD (satisfies GNF rules)
6. E -> eE | eF (satisfies GNF rules)
7. F -> SeF (satisfies GNF rules)

Conclusion

Out of the given productions, only the production S -> aB violates the rules of Greibach Normal Form. Thus, there is only 1 production that violates the rules of GNF in the given grammar.

Top Courses for GATE

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Other Engg Branches

Related Exams

Company