5,232 views

Which one of the following statements is FALSE?

1. There exist context-free languages such that all the context-free grammars generating them are ambiguous
2. An unambiguous context-free grammar always has a unique parse tree for each string of the language generated by it

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

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

### 1 comment

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)

1. This is true for inherently ambiguous language
2. Always correct, that's why called unambiguous
3. NPDA is a super set of DPDA, hence it's FALSE
4. Finite language is always regular

edited

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,

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