I know that converting an ambiguous context free grammar (CFG) to be in Chomsky Normal Form (CNF) might make it unambiguous, but is it a method that necessarily makes any CFG unambiguous? My knowledge tells me that the only way to prove a CFG to be ambiguous is to build two different parse trees, but i cannot find the relevance with the above statement. And, since proving a CFG to be unambiguous is undecidable, I don't know how to prove the statement to be correct as well. Please give some ideas or a counter example.
2026-03-26 02:54:57.1774493697
Is there a context free grammar that is both in Chomsky Normal Form and ambiguous?
1.8k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
No, it is not: there are context-free languages that are inherently ambiguous, meaning that they have no unambiguous grammar. The accepted answer at this question sketches a proof of inherent ambiguity of a particular context-free language. Since any context-free language has a grammar in Chomsky normal form, this shows that such a grammar can be ambiguous.