0
3.5kviews
Find the CNF equivalent to

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

1 Answer
0
311views

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$

Please log in to add an answer.