DSSSB TGT 2021
April 13, 2024GATE 2012
April 13, 2024GATE 2007
| Question 53 |
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?
| Both P and Q are true | |
| P is true and Q is false | |
| P is false and Q is true | |
| Both P and Q are false |
Question 53 Explanation:
Every regular grammar is LL(1) is false, as the grammar may have left recursion or left factoring or also it is possible that grammar is ambiguous.
For ex: Consider a regular grammar
S -> aS | a | ϵ
this grammar is ambiguous as for string “a” two parse tree is possible.
Hence it is regular but not LL(1).
For ex: Consider a regular grammar
S -> aS | a | ϵ
this grammar is ambiguous as for string “a” two parse tree is possible.
Hence it is regular but not LL(1).
But every regular set has a language accept or as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
Correct Answer: C
Question 53 Explanation:
Every regular grammar is LL(1) is false, as the grammar may have left recursion or left factoring or also it is possible that grammar is ambiguous.
For ex: Consider a regular grammar
S -> aS | a | ϵ
this grammar is ambiguous as for string “a” two parse tree is possible.
Hence it is regular but not LL(1).
For ex: Consider a regular grammar
S -> aS | a | ϵ
this grammar is ambiguous as for string “a” two parse tree is possible.
Hence it is regular but not LL(1).
But every regular set has a language accept or as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.