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

Answer: option C

LL Grammar: Grammars which can be parsed by an LL parser.

LL parser: Parses the input from Left to right, and constructs a Leftmost derivation of the sentence(i.e. it is always the leftmost non-terminal which is rewritten). LL parser is a top-down parser for a subset of context-free languages.
An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence and can do it without backtracking.

Consider a Grammar $G$:

• $S \rightarrow a\mid aa$

This grammar is Regular but cannot be parsed by a LL(1) parser w/o backtracking, because here, lookahead is of 1 symbol only and in the grammar for both productions, parser while looking at just one(first) symbol, which is $a$, fails to select the correct rule for parsing.

Hence, not every Regular grammar is LL(1); Statement P is False.

LR Grammar: Grammars which can be parsed by LR parsers.

LR Parser: They are a type of bottom-up parsers that efficiently handle deterministic context-free languages(DCFL) in guaranteed linear time.

All Regular Languages are also DCFL. Hence, they all can be parsed by a LR(1) grammar. 

Hence, Statement Q is True.

Comments

For a regular language there can be many regular grammars.And regular grammar can be ambiguous as well as left recursive  so every regular grammar can not be LL(1) because  LL(1) grammars should be unambiguous.

LR(1) grammars are those grammars which derive the the language which is DCFL.Now all the regular languages are DCFL so there must be one grammar for a regular language which is LR(1).

But if the second statement is also about the regular grammar then will this also be false?Because regular grammar can be ambiguous.

Please comment and validate my understanding @Arjun.

regular grammar can be ambiguous but the regular language is not inherently ambiguous.So is DCFL.

---

@Ayush if grammer is S--->Sa|a then there wouldn’t be any such conflict and it would be LR (0) right ??

---

One key point to take from here is that Every Regular Set have atleast one grammar which is unambiguous. Why?

If there is a Regular Set which has no unambiguous grammar i.e. all the grammars that we generate are ambiguous, then that grammar cannot be accepted by LL(1) as it only accepts unambiguous grammars. But since every regular sets have LL(1) grammar, it also implied that for EVERY regular set we can have a unambiguous grammar.

Answer 2

P: This is false.

Every regular language is LL(1) meaning we have a LL(1) grammar for it. But we can not say same about every Regular Grammar. For example, every regular language can be represented by Left & Right Linear Grammar, where Left Linear Grammar is not LL(1), Right linear is.

Example $aa$* we can represent this as $S \rightarrow Sa|a$ which is not LL(1) ,but $S \rightarrow a|aS$ is LL(1).

Q: This is true because of every LL(1) is LR(1).

All regular sets have Right recursive grammar, which is LL(1) & Every LL(1) is LR(1).

We can also say that LR(1) accepts DCFL & Regular languages are subset of DCFL.

So Answer is C.

Comments

Multiple regular grammar can have the same regular set. So for a regular set, you may show me a ambiguous grammar and say that it is not LR(1), I will counter it by showing you another grammar for the same regular set and say that it is LR(1).

So, I am also confused now.

---

Same here, in confusion state.

---

LR(1) is the property of grammar, not of language.

Answer 3

P : FALSE because a left-linear regular grammar can be left-recursive and left recursive languages cannot be LL(1)

Q: TRUE because every regular set (or language) has a right-linear deterministic (or left-factored) unambiguous grammar and thus, every regular language can have an LL(1) grammar. Since every LL(1) grammar is also LR(1), Q is true.

NOTE : For, every regular language, there exists an unambiguous grammar because regular languages are acceptable by DFAs and unambiguity is a property of non-determinism.

Comments

@Vishal Goel

NOTE : Every regular language is inherently unambiguous

this statement is not correct,

if a language L is inherently unambigous it means, that every grammer generating L will be unambigous....this is not true..

for eg:

let regular language, L = {a}

now one grammer for L could be, S->aA/a   A->$\epsilon$..........and this grammer is ambigous.

---

By the term "inherently unambiguous language", I had meant that there exists at least one unambiguous grammar for the language. But, I think, the term doesn't really exist. So, I have edited my answer. Thanks for pointing it out.

Answer 4

since every regular set can be written is left recursive as well in right recursive and a grammar written in right recursive is LL(1) and we know every LL(1) is LR(1) . So it is true

Comments

$\\A\rightarrow aA/a/\epsilon$

It’s Right recursive and regular grammar but not LL(1) grammar.

It’s not even unambiguous grammar.