Discussion
Given a Context-Free Grammar \(G\) as follows:
\(S \rightarrow Aa \mid bAc \mid dc \mid bda\)
\(A \rightarrow d\)
Which ONE of the following statements is TRUE?
Answer: C
G is LALR(1), not SLR(1).
Follow(A) = {a, c}, because A is followed by a in S → Aa and by c in S → bAc. Consider the state reached after b then d. It contains A → d. (from S → b.Ac) and S → bd.a.
SLR(1) reduces A → d on every symbol in Follow(A), including a, but the item S → bd.a shifts a: a shift-reduce conflict, so G is not SLR(1).
With LR(1) lookaheads, A → d. in that state carries only the lookahead c (from S → bAc), so there is no conflict with shifting a. The state reached by d alone has A → d. with lookahead a and S → d.c shifting c, again without conflict. No two LR(1) states with the same core have clashing lookaheads, so merging them for LALR(1) introduces no conflict: G is LALR(1), and therefore CLR(1) too. That rules out the other three options.
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