The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.1k views

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

  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.
asked in Compiler Design by Veteran (59.6k points)
edited by | 1.1k views

1 Answer

+40 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 :

  1. 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 \}$


  1. 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) = \{\}$


  1. 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 \}$

answered by Boss (15.5k points)
edited by
+2
Solving for an instance does not prove the general case, right? Is there some way to prove for the general case?
0
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.

0
so what is the final answer ??
0
@Arjun sir can you please have look at this question and answer?
+1
@dan31

You are wrong, in your example, in all 3 cases follow(A) will be {a, b} only.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,871 questions
47,531 answers
146,031 comments
62,297 users