Question

Consider the following augmented grammar with terminals {#, @, <, >, a, b, c}.

$S' → S$
$S → S\#cS$
$S → SS$
$S → S@$
$S → <S>$
$S → a$
$S → b$
$S → c$

Let I₀ = CLOSURE({ S' → • S }). The number of items in the set GOTO(GOTO(I₀, <), <) is  .

Hint:

In LR parsing, always apply CLOSURE after each GOTO to count all reachable items.

Answer 1

Correct Answer: 8

To solve the problem, we need to determine the number of items in the set GOTO(GOTO(I₀, <), <) given the augmented grammar.

First, define I₀ as CLOSURE({ S' → • S }). The closure of I₀ includes the initial item and any items that can be derived from the grammar where the non-terminal is on the right after a dot (•).

Step 1: Compute CLOSURE(I₀) 
1. Start with:

S' → • S2. Since S is to the right of the dot, include productions for S from the grammar:S → • S\#cS
S → • SS
S → • S@
S → • <S>
S → • a
S → • b
S → • cThis defines I₀.

 

Step 2: Compute GOTO(I₀, <)
Apply the GOTO function with symbol < on I₀:
1. Find items where < is right after the dot:

S → • <S>2. Move the dot past <:S → < • S>3. Calculate closure for items with new dot position, adding items where S is to the right of the dot:S → • S\#cS
S → • SS
S → • S@
S → • <S>
S → • a
S → • b
S → • cDenote this set as I_A.

 

Step 3: Compute GOTO(I_A, <)
Apply the GOTO function with symbol < on I_A:
1. Find items where < is right after the dot (none exist, since dot does not precede < in I_A).

Step 4: Conclusion
No new items are added to GOTO(GOTO(I₀, <), <) set since I_A has no valid < transitions. Hence, the number of items ultimately settles only on the items derived:

• S → < • S>
• S → • S\#cS
• S → • SS
• S → • S@
• S → • <S>
• S → • a
• S → • b
• S → • c

Thus, there are 8 items.

 

This count confirms that the solution's value 8 fits the given range [8,8].