context-free-grammarcomputation-theorycontext-free-languagechomsky-normal-form

Is it possible for an ambiguous CFG convert into CNF and becomes unambiguous?

Is it possible for an ambiguous context-free grammar(CFG) to convert into Chomsky Normal Form(CNF) and becomes unambiguous?

Solution

  • Sure. All you really need is a single example to show this is possible. Consider the ambiguous grammar

    S :- A | B
A :- a
B :- a

    This grammar is equivalent to the following grammar in CNF

    S :- a

    This grammar is not ambiguous.