Find the CNF equivalent to

0

4.2kviews

Find the CNF equivalent to

written 6.8 years ago by

pratikj2208 • 150

modified 5.7 years ago by

prashantsaini • 0

S -> aAbB , A -> aA|a , B -> bB|b

automata theory

ADD COMMENT EDIT

1 Answer

0

401views

written 6.6 years ago by

teamques10 ★ 70k

modified 6.5 years ago by

ankitpandey • 100

Solution:

$G = \{ $

$S \rightarrow aAbB$

$A \rightarrow aA / a$

$B \rightarrow bB / b$

$ \} $

Let $A_1 \rightarrow a$ $B_1 \rightarrow b$

$\therefore S \rightarrow A_1 AB, B$

$A \rightarrow A_1 A | a .... in CNF$

$B \rightarrow B_1 B | b .... in CNF $

$\therefore S \rightarrow A_1 A_2$

$ A_2 \rightarrow A A_3$

$A_3 \rightarrow B_1 B$

$ \therefore $ Final G in CNF is

$S \rightarrow A_1 A_2$

$A_1 \rightarrow a$

$ B_1 \rightarrow b$

$ A_2 \rightarrow AA_3$

$A_3 \rightarrow B_1 B$

$A \rightarrow A_1 A | a$

$ B \rightarrow B_1 B|b$

ADD COMMENT EDIT

Please log in to add an answer.