The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 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.

+43 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 \}$

+3

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users