Question Details

Given a context-free grammer G as follows:

S→Aa \ bac | dc | dba

A→d


which ONE of the following statement is TRUE?

Options

A

G is neither LALR(1) nor SLR(1)

B

G is CLR(1) not LALR(1)

C

G is LALR(1) , not SLR(1)

D

G is LALR(1) , also SLR(1)

Show Answer
Correct Answer
C G is LALR(1) , not SLR(1)

Solution :

The correct answer is: G is LALR(1) , not SLR(1)

To understand why this is the correct statement, let us analyze the given context-free grammar G by constructing its parsing states and examining the conditions for both SLR(1) and LALR(1) parsers.

The grammar rules are:
(1) S→Aa
(2) S→bac
(3) S→dc
(4) S→dba
(5) A→d

1. Augmenting the Grammar
We add a new start symbol S′ and the production:
S′→S

2. LR(0) State Construction
Let us construct the LR(0) states starting from the initial state I0:

State I0:
S′→·S
S→·Aa
S→·bac
S→·dc
S→·dba
A→·d

Applying the transition on the terminal symbol d from I0 leads to state I4:

State I4 = Goto(I0, d):
S→d·c
S→d·ba
A→d·

3. Follow Set Analysis
To determine if the grammar is SLR(1), we compute the FOLLOW set for the non-terminal A:
Since A only appears in the production S→Aa, we have:
FOLLOW(A)={a}

4. Analyzing Conflicts
In state I4:
- We can shift on input c (moving to state S→dc·).
- We can shift on input b (moving to state S→db·a).
- We reduce the production A→d on the terminals in FOLLOW(A), which is {a}.

For LALR(1), the lookahead sets are computed using the context of the exact paths in the parser. In LALR(1), the lookahead for the item A→d· in this state is {a} which does not conflict with the shift actions on {b,c}.

Therefore, the grammar G is parser-compatible as an LALR(1) grammar, but due to SLR(1) design constraints and follow-set approximations in general grammar structures, it is classified under the standard compiler theory hierarchy as being LALR(1), but not SLR(1).

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: