The Gateway to Computer Science Excellence

+25 votes

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).

- FOLLOW(A) and LFOLLOW(A) may be different.
- FOLLOW(A) and RFOLLOW(A) are always the same.
- All the three sets are identical.
- All the three sets are different.

+51 votes

Best answer

**Ans - a,b, **LFollow may be different but RFollow and Follow will be same

Consider a Grammar -

$S \rightarrow AB$

$A \rightarrow a$

$B \rightarrow b$

Now only string derivable is $\{ ab \}$.

Let's find Follow(A) in all cases :

**Follow(A)**- set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential " form

$S \rightarrow AB \rightarrow Ab \rightarrow ab$

Here, we notice only '$b$' can appear to the right of $A$.

Follow$(A) = \{ b \}$

**LFollow(A)**- set of terminals that can appear immediately to the right of non-terminal $A$ in some "left sentential" form

$S \rightarrow AB \rightarrow aB \rightarrow ab$

Here, we notice no terminal can appear to the right of $A$.

LFollow$(A) = \{\}$

**RFollow(A)**- set of terminals that can appear immediately to the right of non-terminal $A$ in some "right most sentential" form

$S \rightarrow AB \rightarrow Ab \rightarrow ab$

Here, we notice only '$b$' can appear to the right of $A$.

RFollow$(A) = \{ b \}$

+4

Solving for an instance does not prove the general case, right? Is there some way to prove for the general case?

+2

If I use below grammar, I get three different sets-

S->AaAb

A->d

Follow(A)= {a,b}

LFollow(A)={b}

RFollow(A)={a}

I think except C, all remaining options are correct.

Although for a specific sentence like S->ab (any derivation gives same sentence), the given ans is right.

52,345 questions

60,497 answers

201,862 comments

95,319 users