The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

**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 \}$

+2

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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,531 answers

146,031 comments

62,297 users