Question: Find the CNF equivalent to
0

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

Mumbai University > Information Technology > Sem 4 > Automata Theory

automata theory • 264 views
ADD COMMENTlink
modified 4 months ago by gravatar for RB RB ♦♦ 110 written 8 months ago by gravatar for pratikj2208 pratikj22080
0

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 COMMENTlink
modified 4 months ago by gravatar for Ankit Pandey Ankit Pandey ♦♦ 70 written 4 months ago by gravatar for RB RB ♦♦ 110
Please log in to add an answer.