Ask
Login
0
1.8kviews
Explain algorithm for the conversion of a Context Free Grammar(CFG) to Chomsky Normal Form(CNF) and use it to convert the following CFG to CNF:
written 6.4 years ago by gravatar for teamques10 teamques10 ★ 65k •   modified 2.3 years ago

Mumbai University > Informatica Technology > Sem 4 > Automata Theory

Marks: 10M

S => bA|aB

A => bAA|aS|a

B =>aBB|bS|b
automata theory
ADD COMMENT EDIT
1 Answer
0
8views
written 6.4 years ago by gravatar for teamques10 teamques10 ★ 65k •   modified 6.4 years ago

For CNF, A => BC(two nonterminals)

Or

A => a(one terminal)

Consider S => bA

S => BA which is a CNF (substituting B =>b)

Consider S => aB

S => AB which is CNF(substituting A => a)

Consider A =>aS

Let $C_1 =\gt a$

$A =\gt C_1S$ which is …

Create a free account to keep reading this post.

and 4 others joined a min ago.

ADD COMMENT EDIT
Please log in to add an answer.