Consider the following grammars. Names representing terminals have been…
2007
Consider the following grammars. Names representing terminals have been specified in capital letters.
Which one of the following statements is true?
- A.
G1 is context-free but not regular and G2 is regular
- B.
G2 is context-free but not regular and G1 is regular
- C.
Both G1 and G2 are regular
- D.
Both G1 and G2 are context-free but neither of them is regular
Attempted by 8 students.
Show answer & explanation
Correct answer: D
The grammar G1 contains a recursive production with the same non-terminal on both sides of the rule (stmt → WHILE expr stmt), which is characteristic of context-free grammars. However, it cannot be regular because the WHILE construct requires matching parentheses or nested structures that a finite automaton cannot track. Similarly, G2 has recursive productions (expr → expr + expr) that also require context-free parsing. Therefore, both grammars are context-free but not regular, making option D correct.