in Theory of Computation
358 views
5 votes
5 votes
How to know whether  L(G) is inherently ambiguous or not for a particular grammar 'G'  ? Is there any algorithm for it ?
in Theory of Computation
358 views

4 Comments

no...there is no algo...
0
0
What is it meant by inherently ambiguous?
0
0
@Naveen , A Language is called Inherently Ambiguous if all the grammars which generates this language that all are ambiguous ie. if no unambiguous grammar exist for a language then it is called Inherently Ambiguous... "Whether a CFL is inherently ambiguous or not ?" This problem is undecidable .. Bcoz there is no algo for it...But I don't know it is undecidable for csl , recursive , recursive enumerable , non-recursive enumerable languages or not ?
1
1
there is no any algorithm for finding whether a grammer is ambigious or not .it is undecidable for CFL,CSL,RECURSIVE,RECURSIVE ENUMERABLE because if lower level of grammer(CFG) is undecidable so automatically higher level of grammer will be undecidable.
0
0

Please log in or register to answer this question.