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)

---

also; $Regular$, $DCFL$, $CSL$, $Recursive$, and $Recursively\ enumerable$ languages don't have inherent ambiguity

as for these there exists a deterministic parsing algorithm for them 
 

• Regular lang has : FA, NFA, Regex (all equivalent)
• DCFL : has deterministic PDA
• CSL : has LBA (finite length tape turing m/c) & NDTM ~ DTM
• Recursive: has Decider (a turing m/c which halts for both acceptance and rejecting)
• Recursive enumerable : has a recognizer (a turing m/c halts for acceptance, might loop forever or halt for w not belonging to language)
  
  NOTE:  don't get confused b/w ambiguity and decideability, Recursive enumerable is free from inherent ambiguity because there exits a turing m/c for all recursively enumerable langaugea and NDTM(non deterministic turing m/c) are equivalent to deterministic turing m/c hence there exists a derteminisic way to express re language, similary for Regular languages there exists an equivalent DFA for all NFA's
  
  CFL only has a PDA, which is non-deterministic and there exist no equivalent determinsitc PDA for PDA as expressive power of DPDA and PDA are different, that's why only CFL has inherent ambiguity
  
  PDA : is inherently non-deterministic, and there exists no algo to convert a PDA into its equivalent DPDA

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