Consider the following augmented grammarS→aAb |ebA→e |fFind the number of states in LR(0) construction.a)1b)5c)7d)9Correct answer is option 'D'. Can you explain this answer?

Question

Answer

LR(0) Construction

Given Grammar:
S → aAb | eb
A → e | f

Step 1: Augment the Grammar
We need to augment the grammar by adding a new start symbol and a production for it.
S' → S

The augmented grammar becomes:
S' → S
S → aAb | eb
A → e | f

Step 2: Compute the Closure of the Start State
The closure of the start state is the set of LR(0) items that can be derived from the start state.

The start state is {S' → .S}, where the dot indicates the position of the parser.

The closure of the start state is:
{S' → .S, S → .aAb, S → .eb, A → .e, A → .f}

Step 3: Compute the GOTO Sets
For each LR(0) item, compute the GOTO sets by finding the items that can be derived from the current item by shifting the dot one position to the right.

GOTO(I, X) = Closure({A → αX.β | A → α.Xβ ∈ I})

For example, GOTO({S' → .S}, S) = {S' → S.}

Step 4: Construct the LR(0) States
Start with the closure of the start state as the initial state.

I0 = Closure({S' → .S, S → .aAb, S → .eb, A → .e, A → .f})

Next, for each item A → α.Xβ in Ii and for each grammar symbol X, compute GOTO(Ii, X) and add it as a new state if it is not already in the set of states.

Continue this process until no new states can be added.

Step 5: Determine the Number of States
Count the number of states obtained in the LR(0) construction.

In this case, we have 9 states:

I0 = {S' → .S, S → .aAb, S → .eb, A → .e, A → .f}
I1 = {S' → S.}
I2 = {S → a.Ab, A → .e, A → .f}
I3 = {S → aA.b}
I4 = {A → e.}
I5 = {S → .eb}
I6 = {A → .e}
I7 = {S → aAb.}
I8 = {A → .f}

Therefore, the correct answer is option D) 9.

Similar GATE Doubts

Consider the following grammar :S→ aAb | ScA→ d | Sd | SThe above grammar is

Consider the following expression grammar G.E - E - T | TT - T + F | FF - (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.

Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________. Correct answer is '6'. Can you explain this answer?

Consider the following grammar:S → aSBdB → bThe number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ________. Correct answer is '7'. Can you explain this answer?

Top Courses for GATE

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Other Engg Branches

Related Exams

Company