GATE CSE 1998 | Question: 14

Question

• A. 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)$?

• B. 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.

• C. Is $L_2$ inherently ambiguous?

Comments

Can anybody explain the B part??

Answer 1

$(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. 

Comments

Yes, non-determinism does not imply "inherent ambiguity". But determinism do imply no "inherent ambiguity". So, how to formally prove a language to be inherently ambiguous?

---

First case : language is not deterministic.

Second case: Grammar for language is Ambiguous, (that is undecidable).

---

But is it enough? I mean if an ambiguous grammar exist for a CFL which is not deterministic, that makes it inherently ambiguous?

---

No, it is not enough. as per definition , we need to say every possible grammar for language is ambiguous. Intuitively we can say, that every grammar will contain some set of productions that will be lead to ambiguity. 

Afaik, no formal way to prove that. 

---

@Praveen Saini  as mentioned in the question, for language L2, $i,j,k,l>=1$ but the grammar given by you can generate null string, right?

---

Instead of $S_1 \to \epsilon$ and  $S_2 \to \epsilon$, productions should be  $S_1 \to ab$ and  $S_2 \to ab$ as $i,j,k,l >= 1$

The smallest string in the language will be $abab$.

---

how to solve such questions. Please tell any source for learning and practising

---

@Manoja Rajalakshmi A ma'am same doubt

---

They asked to use grammar in part a but in the answer why did we take completely new set of productions?

---

@commenter commenter 

we are not using completely new set of productions...(these are just 5 additional production)

S1 in new productions is also there in part a. So remaining productions of part (a) are also considered.

---

@Praveen Saini @Arjun sir , L2 in the selected answer only gives either  a^i b^j or a^k b^l  (i.e only equal no of a's and b's)....But it does not generate the grammar like ex:{a^2b^3 a^5b^5} even it is a part of above L2 right??

what i want to say is when i!=j we should generate k=l but it should also contain i a's and j no of b's......with k (=l) no of a's and b's followed by it....or viceversa....can the above given grammar produce this??/

---

For (a) we should also have n,m>0 right?

---

Why is it tagged under compiler design? This question is clearly from TOC. Although TOC and CD are closely related, it still makes more sense to have such questions under TOC instead of CD. In the GO pyq book there are 41 questions under Grammar section of CD and I feel that some of them should also have been tagged under TOC

---

Constraints on $n$ and $m$ should also be specified in part($a$) as the language in the answer includes $\{a,b\}$ also but it's not in the language given by the grammar.

Also, as the question says, USE THE GIVEN GRAMMAR and add productions, so are we allowed to change the start symbol as the grammar is $G_1 = (N,T,P,S_1)$ where the start symbol is $S_1$?

---

Please someone help me with this

$L_{1} = \left \{ {a^ib^ja^kb^l | i,j,k,l \geq 1,i=j \, and \, k=l}\right \} \\L_{2} = \left \{ {a^ib^ja^kb^l | i,j,k,l \geq 1,i=j \,or\, k=l} \right \} \\Is \,\,\,L_{1}\subset L_{2}$

---

yes it is.

---

But it seems none of them are preserving that property

My additional set of 5 productions are:

$L_{2} = \left \{ a^{i}b^{j}a^{k}b^{l},i=j\ and\ k=l \right \}\cup\left \{ a^{i}b^{j}a^{k}b^{l},i!=j\ and\ k=l \right \}\cup\left \{ a^{i}b^{j}a^{k}b^{l},i=j\ and\ k!=l \right \} \\S\rightarrow S_{2}S_{2}/S_{1}S_{2}/S_{2}S_{1} \\ S_{2}\rightarrow aS_{2}b/ab$

Answer 2

a)L(G1)={aⁱb^j |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

Comments

how do we prove the c) part like is there any shortcut for it??

---

also in b) production rules are more than 5

Answer 3

b)

S-->  S1S2 / S2S1

S1--> aS1b / ϵ

S2-->AB

A-->aA/a

B-->bB/b

just added 4 new extra  productions

Answer 4

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