2
$\begingroup$

Does transforming a CFG to Chomsky normal form make it unambiguous? And if not, is there a technique to convert a CFG G to an equivalent CFG G', so that G' is both unambiguous and LL(1)?

$\endgroup$
  • $\begingroup$ Related question. $\endgroup$ – Raphael Nov 12 '16 at 19:25
  • $\begingroup$ An LL(1) grammar is necessarily unambiguous (by definition) but there are unambiguous languages which do not have LL(1) grammars. $\endgroup$ – rici Nov 13 '16 at 2:04
8
$\begingroup$

There are inherently ambiguous context-free languages, and like all context-free languages they have grammars in Chomsky normal form, so transforming a CFG to Chomsky normal form doesn't necessarily make it unambiguous. For the same reason there is no technique to convert an arbitrary context-free grammar to one which in unambiguous.

Deciding whether a given context-free grammar is ambiguous, or whether a given context-free grammar generates an inherently ambiguous language, is undecidable. This doesn't necessarily mean that there is no procedure that converts any context-free grammar into an unambiguous one given that the language isn't inherently unambiguous, but it does make the existence of such an algorithm somewhat doubtful.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What algorithms are there (if they exist) for finding unambiguous versions of restricted forms of CFGs? Of course, it would have to be not a DCFL (since they always have unambiguous grammars). $\endgroup$ – Ryan Nov 12 '16 at 22:08
  • $\begingroup$ Unfortunately I'm not an expert in the area. $\endgroup$ – Yuval Filmus Nov 12 '16 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.