1,801 views
5 votes
5 votes
For which of the following languages a LL(1) grammar does not exist?
  1. $\{a^n o b^n \mid n \geq 1\} \cup \{ a^n  b^{n} \mid n \geq 1 \}$
  2. $\{ a^n b^m \mid m,n \geq 0 \}$
  3. $\{a^ib^j\mid i\geq j\}$
  4. $\{a^ib^j\mid i= j\}$

1 Answer

3 votes
3 votes

An $LL(1)$ grammar has the following properties

  1. It should NOT be ambiguous
  2. It should NOT have common prefix problem.(it should be left factored)
  3. It should NOT have left recursion.

The $LL(1)$ grammar for the given languages are as follows :-

 

Option $A.$

$\{a^n o b^n \mid n \geq 1\} \cup \{ a^n  b^{n} \mid n \geq 1 \}$

$S \rightarrow aAb$

$A \rightarrow aAb| \epsilon | o$


Option $B.$

$\{ a^n b^m \mid m,n \geq 0 \}$

$S \rightarrow AB | \epsilon$

$A \rightarrow aA' $

$A' \rightarrow \epsilon | A $

$B \rightarrow bB' $

$A' \rightarrow \epsilon | B $


Option $C.$

$\{a^ib^j\mid i\geq j\}$

$S \rightarrow aS'$

$S' \rightarrow Sb | Ab$           ( Here $FIRST(S) \cap FIRST(A) \neq \phi $ )

$A \rightarrow aA' $

 $A' \rightarrow \epsilon | A$

So this is $NOT$ a $LL(1)$ grammar.


Option $D.$

$\{a^ib^j\mid i= j\}$

 

if $i,j \geq 0 $

 $S \rightarrow \epsilon |aSb$

 

if $i,j >0 $

$S \rightarrow aS'$

$S' \rightarrow b|Sb$


$\therefore$ For option $C$ we can't generate $LL(1)$ grammar.

Answer:

Related questions

6 votes
6 votes
2 answers
1
Arjun asked Jan 26, 2019
1,687 views
If we merge states in LR(1) parser to form a LALR(1) parser, we may introduceshift-reduce conflictreduce-reduce conflictno extra conflictboth shift-reduce as well as redu...
4 votes
4 votes
2 answers
2
Arjun asked Jan 26, 2019
835 views
Suppose we have a rightmost derivation which proceeds as follows:$\begin{array}{ccc}S &\rightarrow & Aabw \\ & \rightarrow &ABw \end{array}$Which of the following is a po...
3 votes
3 votes
1 answer
4