a) Convert the given CFG into CNF $S \rightarrow bA \mid aB, A \right…

Previous year question for Theory of Computation.

Question

a) Convert the given CFG into CNF

$S \rightarrow bA \mid aB, A \rightarrow bAA \mid aS \mid a, B \rightarrow XBB \mid YS \mid b$?

b) Construct CFG to generate the following :

i) The set of all strings over \{a,b\} containing twice as many a's as b's

ii) \{a^n b^m \mid m \neq n, m, n \ge 1\}.