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

Here not every DCFL is LR(1).

Eg:a^nb^n

---

https://gatecse.in/lr-parsing-part-2-language-of-ll-and-lr-grammars/

Read this article written by Arjun sir. All doubts be cleared

---

@raja11sep

Your point "" is correct.

I just wanted to add, there are LL(1) grammars with epsilon which also are SLR(1).

Example :

S  -> aS
S  -> ε

---

@sreenadh annaluru

LR(1) grammar for $a^{n} b^{n} $ :

S  -> a S b
S  -> ε 

"Every DCFL has a LR(1) grammar is true"

Refer :  Link

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

Same here, in confusion state.

---

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

---

There are some left linear grammar which are LL(1), some are not.

Likewise, There are some right linear grammar which are LL(1), some are not.

 

Also, every right recursive grammar is not LL(1)

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.

Answer 5

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 6

• 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.