GATE CSE 2019 | Question: 19

Question

Consider the grammar given below:

• $S \rightarrow Aa$
• $A \rightarrow BD$
• $B \rightarrow b \mid \epsilon $
• $D \rightarrow d \mid \epsilon $

Let $a,b,d$ and $\$$ be indexed as follows:$$\begin{array}{|l|l|l|l|} \hline a & b & d & \$ \\ \hline 3 & 2 & 1 & 0 \\ \hline \end{array}$$Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order.(For example, if the FOLLOW set is $(a,b,d, \$)$ , then the answer should be $3210$)

Comments

first(S) = first (A)= first(B) = b , epsilon

Now substitute epsilon in place of B in A-> BD

So first(A) = first(D) = d, epsilon

So this means A can generate b,d, epsilon.

Now if we substitute epsilon in S->Aa then we can get first(S) = a

Note that we are not writing epsilon in first(S) because S can't generate epsilon.

Hence first(S) = {a,b,d}

---

I confused, on that because I thought $'S'$ can generate $\epsilon.$

Now it is clear for me,thanks

---

Same bro

Answer 1

For $\text{Follow(B)} \implies \text{First(D)} = \{ d, \epsilon \}$

Put $\epsilon$ in $II$ production

$\text{Follow (B)} = \text{ Follow (A)} = \{ a\}$

$\text{Follow (B)} = \{ d,a \}$

According to the question writing Follow set in decreasing order:$$\begin{array}{|l|l|} \hline a & d \\ \hline 3 & 1 \\ \hline \end{array}$$Hence $31$ is correct answer

Comments

Thanks

---

@Rishav_Bhatt can the answer be  13 also?

---

@Hrithik Vashishtha If the question had asked in ascending then the answer would have been 13 but the question had asked in descending order that’s why the answer can’t be 13.

Answer 2

Follow of B={d,a}

D is right of B so we take terminal first of D that is d if D is € in such case follow of B=follow of A that is a

So answer is ad = 31

Answer 3

Answer is: 31

1. Here B is in the right side of the Production Rule:

$A\rightarrow BD$                 $\therefore FOLLOW(B)= FIRST(D)$ 

$FIRST(D)=d$ (Therfore it is in $FOLLOW(B)$)

Finally Putting $D\rightarrow \varepsilon$ in the Production $A\rightarrow BD$   then $FOLLOW(B)=FOLLOW(A)$

$FOLLOW(A)=a$ (From the Production rule $S\rightarrow Aa$)

$\therefore FOLLOW(B)= (d,a)$

As we have to write answer in the Decreasing order of INDEX (a,d) $\rightarrow$ (31)