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

1
votes

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

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

1 Answers

1
votes

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.