edited by
1,397 views
1 votes
1 votes

Is every language that is generated by a NDCFG (Non Deterministic Context Free Grammar) , CSG (Context Sensitive Grammar) and Unrestricted Grammar inherently ambiguous ?

I think so because they dont have a DPDA accepting that language. And as far as I understand if a language is not inherently ambiguous, it must have a DPDA accepting it. 

So, if that is true, then the language {anbn, n>=0} U {anb2n, n>=0} is inherently ambiguous, because there is no DPDA accepting that language. But if I see the grammar for the language:

          S -> A | B

         A -> aAb | ε

         B -> aBbb | ε

and I consider the string "aabb", I dont get two parse trees (which is a necessity for a grammar to be ambiguous ! And a language can be "inherently ambiguous" only if it has NO UNAMBIGUOUS GRAMMAR REPRESENTATION

But here we get an unambiguous grammar for a language that is not accepted by DPDA. So my question is : is this language inherently ambiguous?

Also in case of CSL and REC, there are no "parse trees" as such. So how do I determine if the language is inherently ambiguous or not? 

edited by

Please log in or register to answer this question.

Related questions

–1 votes
–1 votes
1 answer
1