edited by
4,328 views
12 votes
12 votes
  1. Let $G_1 = (N, T, P, S_1)$ be a CFG where, $N=\{S_1, A, B\},T=\{a, b\}$ and $P$ is given by$$\begin{array}{l|l}
    S_1 \rightarrow a S_1 b &S_1 \rightarrow a B b \\
    S_1 \rightarrow a A b & B \rightarrow Bb\\
    A \rightarrow a A & B \rightarrow b\\
    A \rightarrow a
    \end{array}$$What is $L(G_1)$?
  2. Use the grammar in Part(a) to give a CFG for $L_2 = \{a^ib^ja^kb^l \mid i, j, k, l \geq 1, i=j \text{ or } k=l\}$ by adding not more than $5$ production rules.

  3. Is $L_2$ inherently ambiguous?

edited by

4 Answers

Best answer
17 votes
17 votes

$(a)$ $L(G_1) = \{a^nb^m \mid n \neq m\}$

$(b)$

  • $S_1\rightarrow S_2S_3\mid S_3S_2 \qquad (2)$    
  • $S_3\rightarrow aS_3b \mid ab \qquad (2)$
  • $S_2 \rightarrow ab\qquad (1)$ 

So, totally $2+2+1 = 5$ extra productions. 

$(c)$ If grammar is ambiguous and no unambiguous grammar is possible for the language, then language is inherently  ambiguous.

Non-determinism of language (if it means, $L$ is not DCFL) + ambiguity for all possible grammars implies inherent ambiguity. Or if a language is deterministic, it is surely not inherently ambiguous. But if a language is not deterministic, it may or may not be inherently ambiguous. 

The given language $L_2$ is the set of strings where number of $a's$ is followed by an equal number of $b's$ and if not, for the remaining part, the number of $a's$ is followed by an equal number of $b's$. This is actually a deterministic language as we do not need to do multiple counts here. Only after the first condition is violated we need to start doing the count for the second part. This makes the language deterministic and hence it cannot be inherently ambiguous. 

edited by
3 votes
3 votes

a)L(G1)={aibj |i,j>1, i>j or j>i}

b)S ->S1S2 | S2S1

S1 -> aS1b | ab

S2 -> S3S4

S3 -> aS3 | a

S4 -> bS4 | b

c) Inherently Ambiguous grammar means there will not be any unambiguity in that grammar

But here we can generate aabbaaab ,aabbbaabb..........these grammar which are unambiguous in nature

So, it is not inherently ambiguous grammar

edited by
1 votes
1 votes
b)

S-->  S1S2 / S2S1

S1--> aS1b / ϵ

S2-->AB

A-->aA/a

B-->bB/b

just added 4 new extra  productions
1 votes
1 votes
A) $L(G_{1}) = \left \{ a^ib^j| i\;!=j \right \}$

B) Additional productions are

$S\rightarrow S_{1}S_{2}/S_{2}S_{1}/S_{2}S_{2} \\S_{2}\rightarrow aS_{2}b/ab$

​​​​​​​C) Language is DCFL, So it’s not inherently ambiguous grammar

Related questions

26 votes
26 votes
2 answers
1
Kathleen asked Sep 25, 2014
6,970 views
Consider the grammarS $\rightarrow Aa \mid b$A $\rightarrow Ac \mid Sd \mid \epsilon$Construct an equivalent grammar with no left recursion and with minimum number of pr...
28 votes
28 votes
1 answer
4
Kathleen asked Sep 25, 2014
8,681 views
Faster access to non-local variables is achieved using an array of pointers to activation records called a stackheapdisplayactivation tree