Regular grammar in TOC

Question

Find the regular grammar for $L=\{a^nb^m \mid n+m \text{ is even}\}$

Answer 1

There are $2$ cases:

1. $n$ and $m$, both are even $\rightarrow (aa)$*$(bb)$*

2.  $n$ and $m$, both are odd $\rightarrow a(aa)$*$b(bb)$*

Regular expression: $\rightarrow (aa)$*$(bb)$* $+$ $a(aa)$*$b(bb)$*

Regular grammer:

$S \rightarrow aaA/aA_{1}/\epsilon$

$A \rightarrow aaA/bbB/\epsilon$

$B \rightarrow bbB/\epsilon$

$A_{1} \rightarrow aaA/bB$

Comments

To get the RG you need to hit and try alot?

---

Yes