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:

2.1kviews

written 7.9 years ago by

teamques10 ★ 70k

• modified 3.9 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

8views

written 7.9 years ago by

teamques10 ★ 70k

• modified 7.9 years ago

For CNF, A => BC(two nonterminals)

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 3 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.