416 views
1 votes
1 votes
which languages among

regular lang

CFL

CSL

REC

REL

have ambiguos grammar and which has unambiguos grammar and which can have both

2 Answers

Best answer
0 votes
0 votes

A grammar is ambiguous if we can drive a string in the language with two different derivation steps.

A language L is called an unambiguous language if there exists an unambiguous grammar that generates L.

If every grammar that generates L is ambiguous, then the language is called inherently ambiguous.

Now,
Regular Languages: Yes there may exist an ambiguous grammar. But that doesn't mean that the language becomes ambiguous.
For regular language L, we always have a regular grammar that generates L and it is not ambiguous.

For ex: S $\rightarrow$ aA / ab
             A  $\rightarrow$ b. 
In this, we can generate the string 'ab' with two different derivation steps. So this grammar is ambiguous. But if can find a different regular grammar that generates the same language L and which is not ambiguous. For Ex: S  $\rightarrow$ ab.

To prove that Regular languages can't be ambiguous we can have a different argument.
For every regular language there exist a DFA and in DFA every step is well determined. To generate a particular string we always have definite steps. So we can't have two ways to generate the string.

DCFL: For DCFL we have deterministic PDA, Where for a particular string we have well-defined steps to generate it. So they are also unambiguous languages. 

CFL: Context free languages may be ambiguous or unambiguous.

 Actually, inherent ambiguity begins from this layer. Therefore upcoming layer can be both ambiguous or unambiguous.
Hence, CSL, Recursive languages, and Recursive enumerable languages may be ambiguous or unambiguous.

selected by
0 votes
0 votes
An ambiguous Grammar is CFG which has two derivation trees for a string belonging to the language.

So Regular language cannot be ambiguous. According to Chomsky Grammar classification, other languages are ambiguous if  we can able to get atlease two derivation trees.

 

Please correct me if   i am wrong.

Related questions

0 votes
0 votes
0 answers
1
RahulVerma3 asked Apr 2
54 views
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
161 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.