GATE CSE 2017 | Set 1 | Question: 17

Question

Consider the following grammar:

• $P\rightarrow xQRS$
• $Q\rightarrow yz\mid z$
• $R\rightarrow w\mid \varepsilon$
• $S\rightarrow y$

What is FOLLOW($Q$)?

• A. $\left \{ R \right \}$
• B. $\left \{ w \right \}$
• C. $\left \{ w,y \right \}$
• D. $\left \{ w,\$ \right \}$

Comments

if you mistakenly got $D$, here is what went wrong

$Follow(Q) = First(RS)$

$First(RS) = \{w,  \epsilon \}$

by seeing $\epsilon$ you would have done this

$Follow(Q) = \{w,  \epsilon \} - \{\ \epsilon\} \\ \ \cup\ Follow(s)$

which is wrong as $First(RS) = \{w,  \epsilon \} - \{\ \epsilon\} \\ \ \cup First(S) = \{w,y\}$

and since $First(RS)$ is $\epsilon$ free so $Follow(Q) =  \{w,y\} $

 

Answer 1

Follow of $Q$ is first of $R$ so we get $\{w\}$

but since $R$ can be Null so we have to check first of $S$ which is $\{y\}$

so FOLLOW $Q=\{w,y\}$

Correct option (C)

Answer 2

correct option is c.

Comments

could u plz tell me how to insert a picture in this

---

Nice explanation. From this answer Follow set find rules can be verified.

---

Nice Explanation :)

Answer 3

\[
\begin{array}{|c|c|c|}
\hline
\textbf{Non-terminal} & \textbf{FIRST} & \textbf{FOLLOW} \\
\hline
P & \{x\} & \{\$\} \\
\hline
Q & \{y, z\} & \{w, y\} \\
\hline
R & \{w, \varepsilon\} & \{y\} \\
\hline
S & \{y\} & \{\$\} \\
\hline

\end{array}
\]
$\text{Follow(Q) ={w,y}}$

Correct Answer : $C$

Answer 4

so C is ans.

Answer 5

In the production: P → xQRS,
FOLLOW (Q) = FIRST (R)
FIRST (R) = {w, ϵ} >br> Since FIRST (R) = {ϵ}, so FOLLOW (Q) → {w} ∪ FIRST(S)
FIRST(S) = {y}
So, FOLLOW (Q) = {w, y}

Answer 6

Answer: C

$$\text{Follow(Q) = First(RS) = First(R) = } \{w,\epsilon\}$$ 

$$\text{But, since R directly generates Null } (\epsilon), \text{ substituting } \epsilon \text{ back in the production of P gives: } $$ 

$$\text{Follow(Q) = First(RS) = First(R)} \cup \text{First(S) - } \{\epsilon\} =\{w,y\}$$ 

$$\text{Note: Back substitution of epsilon vanishes the non-terminal generating NULL and omits epsilon.}$$ 

$$\text{Note: Epsilon NEVER comes in the FOLLOW of a non-terminal and \$ NEVER comes in the FIRST of the same.}$$