in Theory of Computation
5,232 views
23 votes
23 votes

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

in Theory of Computation
5.2k views

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

1 Answer

35 votes
35 votes
Best answer
  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 by

2 Comments

edited by

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.

22
22

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

0
0
Answer:

Related questions