GATE CSE 2007 | Question: 53

Question

Consider the following two statements:

• P: Every regular grammar is LL(1)
• Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

• A. Both P and Q are true
• B. P is true and Q is false
• C. P is false and Q is true
• D. Both P and Q are false

Comments

@raja11sep Nice collection of Imp Points.

---

@Abhrajyoti00 😄

---

This is the best answer for this question.

Answer 1

• P: Every regular grammar is LL(1)

False, because Regular Grammars can be Left Recursive.

 

• Q: Every regular set has a LR(1) grammar

LR(1) grammars = Grammars of Bottom-Up Parsers = Grammars that generate DCFLs.

DCFLs are subsets of RLs. For example, {$a^{n} b^{n} | n>1$} is a subset of $(a+b)^*$

Hence, every regular can generate a DCFL. True.

 

Option C is correct.

Answer 2

A regular grammar can also be ambiguous also
For example, consider the following grammar,                             
S → aA/a
A → aA/ε
In above grammar, string 'a' has two leftmost
derivations. 
(1)   S → aA                      (2)   S → a
      S->a (using A->ε)
And LL(1) parses only unambiguous grammar,
so statement P is False.
Statement Q is true is for every regular set, we can have a regular
grammar which is unambiguous so it can be parse by LR parser. 

So option C is correct choice 

Answer 3

P- Every regular grammar may or may not be LL(1). We cannot assure that. The statement given is assuring that and is hence false.

Q- This says that there is atleast one grammar in the regular set which is LR(1). Which is true.

Therefore option C is correct.

Comments

@arjun sir finally need ur help plz gives the reason why B is correct . i m fade up by above comments all are seems to be confusing to me. i did not get clear explanation for option B till this date plz tell me sir

Answer 4

option A is FALSE because regular grammar can be ambiguous and LL(1) do not parse ambiguous grammar.

S->aA/a   A->ϵ

Some ambiguous grammars can be converted into unambiguous grammars, but no general procedure for doing this as no algorithm exists for detecting ambiguous grammars.

Although left linear grammar is not accepted by LL(1) but we can convert every LLG to equivalent RLG.
Moreover, this is also non-deterministic grammar because First of S= {a,a} and LL(1) grammar can parse non-deterministic grammar also but we can convert every non-deterministic grammar to deterministic grammar as well.

There is a difference between Left linear grammar and left recursion. regular languages are either Left linear or Right linear. . Left recursion is a kind of left-linear grammar.

LR(1) grammar parse D-CFL language and every regular language is also CFL so option B is TRUE