UGC NET CSE | June 2014 | Part 2 | Question: 06

Question

A grammar $G$ is $LL(1)$ if and only if the following conditions hold for two distinct productions $A \rightarrow \alpha \mid \beta$

I. First $(\alpha) \cap$ First $(\beta) \neq \left\{a\right\}$ where $a$ is some terminal symbol of the grammar.

II. First $(\alpha) \cap$ First $(\beta) \neq \lambda$

III. First $(\alpha) \cap$ Follow $(A) = \phi$ if $\lambda \in$ First $(\beta)$

• A. I and II 
• B. I and III 
• C. II and III
• D. I, II and III 

Comments

In ll (2^nd statement) if we assume λ is an empty string, then how can we use an equal operator with the set. I think statement ll is invalid according to math. They need to use { λ } for match like they have done in statement l.

Answer 1

assume

S---> aX |aYb

first(aX)= a

first(aYb)= a

so there will 2 entries for  S in terminal 'a' which violates the rule of LL(1) grammar Bcoz for every variable and for every terminal there can be at most 1 production .

hence ,their intersection should be ∅

first one statement is correct

second one is true with similar reasoning as for first.

now third assume example

1) S-->aSA | ∈

2) A--> C |∈

now take 2) production

first(c)  = c

follow(A) = follow(S) = => first(A)= c,∈,$

now the first(c)∩  follow(A)= c

means there will be again 2 entries  for A in c place that means again violation of LL(1) rules.

so first(c)∩  follow(A)=  ∅  is true.

hence answer is (D)

Comments

Plz post answers in regular font any further. It is very difficult to read.

---

Why option B is true here .. it should be False coz There intersection sud be ∅ 

wats the meaning of λ here?.. plz expain

---

phi means nothing , lemda means empty string

Answer 2

For a grammar to be LL(1) each production must be unique. The following conditions must hold:-

• $First(\alpha )\cap First(\beta )=\phi$

Hence I and II are True.

• If either $\alpha$ or $\beta$ (not both) derive $\epsilon$, then $First(<remaining> )\cap Follow(A )=\phi$

Hence III is True.

Option D

https://www.csd.uwo.ca/~moreno/CS447/Lectures/Syntax.html/node14.html

---

PS: $\phi$ is the empty set

$\lambda$ or $\epsilon$ is the empty string