edited by
7,980 views
37 votes
37 votes

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

  1. FOLLOW(A) and LFOLLOW(A) may be different.
  2. FOLLOW(A) and RFOLLOW(A) are always the same.
  3. All the three sets are identical.
  4. All the three sets are different.
edited by

1 Answer

Best answer
75 votes
75 votes

Ans - A,B, $\textsf{LFOLLOW}$ may be different from $\textsf{FOLLOW}$ but $\textsf{RFOLLOW}$ and $\textsf{FOLLOW}$ will be the same

Consider the following grammar

  • $S \rightarrow AB$
  • $A \rightarrow  a$
  • $B \rightarrow b$

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

Let's find $\textsf{FOLLOW}$(A) in all cases :

  • $\textsf{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$.

          $\textsf{FOLLOW}$$(A) = \{ b \}$


  • $\textsf{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$.

          $\textsf{LFOLLOW}(A) = \{\}$


  • $\textsf{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$.

          $\textsf{RFOLLOW}(A) = \{ b \}$


The above example proves that $\textsf{LFOLLOW}$ may not always be the same as $\textsf{FOLLOW}$ but does not prove that $\textsf{RFOLLOW}$ and $\textsf{FOLLOW}$ will always be the same. 

In $\textsf{FOLLOW}(A),$ we add all terminals which appear on the immediate right of A in some sentential form. 

In $\textsf{RFOLLOW}(A),$ we add all terminals which appear on the immediate right of A in some right sentential form. 

Since a right sentential form is also a sentential form, it is clear that $\textsf{FOLLOW}(A) \supseteq \textsf{RFOLLOW}(A) \to (1)$ 

Now, we have to prove $\textsf{RFOLLOW}(A) \supseteq \textsf{FOLLOW}(A) $ for which we need to show that any terminal which gets added to $\textsf{FOLLOW}(A)$ must also be added to $\textsf{RFOLLOW}(A).$ Or in other words, any terminal which can appear on the immediate right of a non-terminal in some sentential form (a sentential form can be either left sentential or right sentential or neither) must also appear to the immediate-right of the same non-terminal in some $\textbf{right-sentential}$ form. 

A terminal $t$ can appear on the immediate right of a non-terminal $A$ in a sentential form

  1. if $t$ is already like that in the grammar production (say $S \to \dots At\dots$
  2. it $t$ produced by some reduction (say $S\to \dots AB \dots, B \to t)$

Now, since we are looking at $\textsf{immediate right}$ terminal in the sentential form, it means leftmost derivations cannot produce the terminal we need, since here $A$ will be reduced before we do reduction for the non-terminal to its immediate right. In fact the only way we can get this terminal $t$ in a sentential form is if we reduce the immediate right non-terminal of $A.$ If we do the rightmost derivation we are guaranteed to do this and rightmost derivation also ensures that all non-terminals to the right of $A$ are already derived and so we get all possible terminals to the right even in cases where the immediate right non-terminal derives empty string. Thus, $\textsf{RFOLLOW}(A) \supseteq \textsf{FOLLOW}(A) \to (2)$

From (1) and (2), we get $\textsf{FOLLOW}(A) = \textsf{RFOLLOW}(A).$ 

edited by
Answer:

Related questions

23 votes
23 votes
4 answers
2
Kathleen asked Sep 13, 2014
4,673 views
Context-free languages are:closed under unionclosed under complementationclosed under intersectionclosed under Kleene closure
24 votes
24 votes
4 answers
3
Kathleen asked Sep 13, 2014
5,350 views
A computer system has $6$ tape devices, with n processes competing for them. Each process may need $3$ tape drives. The maximum value of n for which the system is guarant...
28 votes
28 votes
5 answers
4
Kathleen asked Sep 12, 2014
8,843 views
A $2-3$ tree is such thatAll internal nodes have either $2$ or $3$ childrenAll paths from root to the leaves have the same lengthThe number of internal nodes of a $2-3$ t...