search
Log In
49 votes
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

in Compiler Design 13.2k views
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.

9 Answers

0 votes
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:

Related questions

18 votes
2 answers
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$
asked Apr 23, 2016 in Compiler Design jothee 2k views
19 votes
2 answers
2
3.6k 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$ ... $B \rightarrow aBB$ $S \rightarrow bAA$ Which of the following strings is generated by the grammar? $aaaabb$ $aabbbb$ $aabbab$ $abbbba$
asked Sep 22, 2014 in Compiler Design Kathleen 3.6k views
20 votes
5 answers
3
4.2k views
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
asked Sep 22, 2014 in Compiler Design Kathleen 4.2k views
12 votes
4 answers
4
2.5k views
Which one of the following is a top-down parser? Recursive descent parser. Operator precedence parser. An LR(k) parser. An LALR(k) parser.
asked Sep 22, 2014 in Compiler Design Kathleen 2.5k views
...