# GATE2007-53

13.2k views

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?

1. Both P and Q are true

2. P is true and Q is false

3. P is false and Q is true

4. Both P and Q are false

1

Hi, all previous GATE questions are already here- you can use the above google searchbar or use Prev Exams link in navbar.

https://gateoverflow.in/1251/gate2007_53

2
There is a difference between Left linear grammar and left recursion. regular languages are either Left linear or Right linear. LL(1) does not accept left recursion. Left recursion is a kind of left-linear grammar. every left linear grammar can be converted into equivalent right linear grammar.

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 

## Related questions

1
2k views
Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules: $S \rightarrow aB$ $S \rightarrow bA$ $B \rightarrow b$ $A \rightarrow a$ ... $B \rightarrow aBB$ $S \rightarrow bAA$ For the string $aabbab$, how many derivation trees are there? $1$ $2$ $3$ $4$
Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules: $S \rightarrow aB$ $S \rightarrow bA$ $B \rightarrow b$ ... $B \rightarrow aBB$ $S \rightarrow bAA$ Which of the following strings is generated by the grammar? $aaaabb$ $aabbbb$ $aabbab$ $abbbba$
Consider the grammar with non-terminals $N=\left\{S,C,S_1\right\}$, terminals $T=\left\{a, b, i, t, e\right\}$, with $S$ as the start symbol, and the following set of rules: $S \rightarrow iCtSS_1 \mid a$ $S_1 \rightarrow eS \mid \epsilon$ $C \rightarrow b$ The grammar is NOT LL(1) because: it is left recursive it is right recursive it is ambiguous it is not context-free