0
2.6kviews
Find the CNF equivalent to
written 5.2 years ago by | modified 4.0 years ago by |
S -> aAbB , A -> aA|a , B -> bB|b
ADD COMMENT
EDIT
1 Answer
written 5.2 years ago by | modified 4.0 years ago by |
S -> aAbB , A -> aA|a , B -> bB|b
written 4.9 years ago by | modified 4.9 years ago by |
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$