The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+37 votes

Consider the following statements about the context free grammar

$$G = \left \{ S \rightarrow SS, S \rightarrow ab, S \rightarrow ba, S \rightarrow \epsilon \right \} $$

  1. $G$ is ambiguous
  2. $G$ produces all strings with equal number of $a$’s and $b$’s
  3. $G$ can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about $G$?

  1. I only
  2. I and III only
  3. II and III only
  4. I, II and III
in Compiler Design by Active (3.3k points)
edited by | 7.3k views
option D correct
yes. You can have a DPDA which puts a A when it reads a 'a' and deletes it when the next 'b' is read. similarly, it can put a 'b" on the stack when a b is read and delete it when the next 'a' is read. In the language generated ab occur together as well as ba. (ii) G is ambiguous. ababab can be generated in 2 ways. You do not talk about a grammar being inherently ambiguous, only a language as inherently ambiguous. Inherently ambiguous CFL can be accepted by NPDA but not DPDA

Prof. Kamala Krithivasan.
can we say that all DCFL are unambiguous and NDCFL are inherently ambiguous?

@codingo1234 You can't say

All DCFL's are unambiguous

because "Ambiguity" is a property of a grammar, not a language.

What you can say though, is

All DCFG's are unambiguous

because DCFG $\rightarrow \exists $ a DPDA $\rightarrow \exists $ an LR(1) grammar and LR(k) grammars are necessarily unambiguous.

But here's the catch: "Inherent Ambiguity", as opposed to plain "Ambiguity", is a property of a language, not a grammar. From Sipser:

As for the question

Are all NDCFL's inherently ambiguous?

The answer is NO. A NDCFL may or may not be inherently ambiguous. That's because a language being NDCF does not mean that it can be generated only by ambiguous grammars. For Example, the language $\{ ww^R \vert w \in (a+b)^*  \} $ is non-deterministic (no deterministic PDA exists that can accept it), but it can be generated by the unambiguous grammar $S \rightarrow aSa \vert bSb \vert \epsilon $


@ thanks that cleared many things


This is the original question and nowhere $3^{rd}$ production seems to be $\epsilon$. It seems to be a terminal of length 1. Then how grammar can be ambiguous

^ is meant to represent lambda, which is another way of writing the null string.

2 Answers

+82 votes
Best answer
  1. True. $G$ is ambiguous. E.g. the string $ab$ has multiple derivation trees like $S \rightarrow SS \rightarrow abS \rightarrow ab$, and $S \rightarrow ab$.
  2. False. $G$ does not produce all strings with equal no. of $a$`s and $b$`s. ($aabb$ cannot be generated).
  3. True. The given grammar $G$ generates the language $(ab+ba)^*$, which is Regular and therefore also DCFL. So, a D-PDA can be designed for $G$.

Hence, the answer is option B.

by Boss (31k points)
edited by
@Arjun sir,
I request you to please this question which i asked today at stackexchange

This is about LR and DCFl.
Please see this.
Thnks in advance :)
I think B is also true

it says equal no. of a's and b's and it generates equal no. of a's and b's


correct me if I am wrong
@ARSHAD no it will not produce all strings having equal no of a's and b's such as aabb.
According to regular expression DPDA is right. But DPDA is not allowed for ambiguity it's NPDA which handle such issues  while here its working fine. How can it happened ? I am confused regarding this issue.

Arjun Sir, Sorry but I still  have a doubt:

I understand that an unambiguous grammar can either generate a DCFL or a NDCFL.

But, you also wrote the following:

A grammer can be 

  • ambiguous -- yes, and the language can be finite, regular, deterministic context-free or non-deterministic context-free

I am not able to understand the above line. How can an ambiguous grammar be finite, regular, deterministic context-free.

Also, could you please tell what is an ambiguous language? I understand what an ambiguous grammar can be. (The grammar which can one more than parse tree), but I do not know what is an ambiguous language.


And also, for the above question, is there an unambiguous grammar available cause it is a regular language?


Thank you




Can someone please give example for Ambigous grammar generating NCFL..

@surbhijain93 @jatin khachane 1 It is simple.

$S \rightarrow A\; | \; a\; | \;\epsilon$

$A\rightarrow \; a$

It is ambiguous grammar because for string 'a' , There are 2 possible parse trees :- $S\rightarrow A\rightarrow a$ and  $S\rightarrow a$ and language is finite. So it is regular, DCFL and  NDCFL. After simplification we can write its equivalent unambiguous grammar but originally it is ambiguous. Word 'ambiguous' is associated with grammar and 'inherently-ambiguous' is associated with languages for which no unambiguous grammar is possible.

The equivalent unambiguous grammar for the given question can be :-

$S\rightarrow A\; | B \;  | \; \epsilon$

$A\rightarrow abA\; | \; abB\;|\; ab$

$B\rightarrow baB\; | \; baA\;|\; ba$



We can say DCFL is NOT inherently ambiguous as there always exits LR(1) grammar for every DCFL which is unambigous..

But this may not be true for may not have atleast one unambigous G for it hence it may /may not be inherently ambigous language

am I right ?

Can you please given one grammar which is ambigous and generating NCFL..(not relevant to ques)


@jatin , yes. right. I have already given one example. You can check Praveen sir's answer for option (C) where language is inherently ambiguous NCFL  here and  here.

–3 votes
answer - D
by Loyal (8.7k points)
The question said that using grammar G's production and then generating string contain equal number of a's and b's not over tha alphabet {a,b}

So in this sense it may be true all three options....

please correct me if I am wrong.....

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
50,093 questions
55,326 answers
86,254 users