Discussion
Which one of the following grammars is free from left recursion?
Answer: B
The grammar free from left recursion is S → Ab | Bb | c; A → Bd | ε; B → e.
A grammar is left-recursive if some nonterminal can derive a string starting with itself. In this grammar, S begins with A, B or c; A begins with B or is empty; B begins with the terminal e. No chain returns to the nonterminal it started from, so there is no left recursion.
The others are left-recursive. S → AB; A → Aa | b has direct left recursion in A → Aa. In S → Aa | B; A → Bb | Sc | ε, S ⇒ Aa ⇒ Sca, indirect left recursion through A. In S → Aa | Bb | c; A → Bd | ε; B → Ae | ε, A ⇒ Bd ⇒ Aed, indirect left recursion between A and B.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development