GATE IT 2004 | Question: 9

Question

Which one of the following statements is FALSE?

• A. There exist context-free languages such that all the context-free grammars generating them are ambiguous

• B. An unambiguous context-free grammar always has a unique parse tree for each string of the language generated by it

• C. Both deterministic and non-deterministic pushdown automata always accept the same set of languages

• D. A finite set of string from some alphabet is always a regular language

Comments

In option A:
Instead of Context free language IF it is DCFL..then it will be FALSE .

As for every DCFL there exists atleast one Unambigous grammar that is LR(1)

Answer 1

• A. This is true for inherently ambiguous language
• B. Always correct, that's why called unambiguous
• C. NPDA is a super set of DPDA, hence it's FALSE
• D. Finite language is always regular

Comments

for proving A true we can take the language $L= \left\{a^n b^m c^m \right\}$ U $\left\{a^n b^n c^m \right\}| m,n>0$ then for that you can write only one possible grammer  $S->S1|S2;$   $S1->AB;$  $A->aA|a;$  $B->bBc|bc$

and for $S2->CD;$ $C-> aCb|ab;$ $D->cD|c$  

then for string  $'aabbcc'$ we have two parse tree  so ambiguous thats why here language is ambiguous bcz  the defination of inherit ambigous for a language L is if  we can form L using many grammer and  each grammer must be ambiguous then we said L is inheritly ambiguous.

---

For option A according to you, @rajan , @Manu Thakur

definition of inherit ambagious for a language L is if  we can form L using many gammer and  each gammer must be ambiguous then we said L is inheritly ambiguous .

Q 1: so for every CFL if Gammer is ambagious then All the Gammer(if possible) generating that CFL are         ambiguous and we can't convert ambiguous gammer to unambiguous gammer.is this correct?

 

Q 2:Can we convert all every ambiguous gammer to equivalent unambiguous gammer?

-->I think checking whether gammer is ambiguous or not is undecidable so converting will be undecidable so ans will be No but I need your confirmation

@srestha any suggestion for above questions