The Gateway to Computer Science Excellence

+7 votes

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$)

+13 votes

Best answer

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

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

+8 votes

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

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

+2 votes

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)**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,228 answers

194,225 comments

95,680 users