The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+5 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

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


    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?

asked in Compiler Design by Veteran (59.7k points)
edited by | 638 views

2 Answers

+5 votes
Best answer

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


  • $S\rightarrow S_1S_2\mid S_2S_1 \qquad (2)$    
  • $S_2\rightarrow aS_2b \mid \epsilon \qquad (2)$
  • $S_1 \rightarrow \epsilon\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. 

answered by Veteran (55.4k points)
selected by
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$.
+2 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

answered by Veteran (104k points)
edited by
how do we prove the c) part like is there any shortcut for it??
also in b) production rules are more than 5

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,493 questions
49,944 answers
65,911 users