Finding a regular grammar for the language L

Question

I know a solution for following question using 4 variables including start variable but not less than 4. Is there a solution using less than 4 variables?

Find a regular grammar for the language L = {a^n * b^m : n,m>=0, n + m is odd} using less than 4 variables including S.

Answer 1

You've provided a correct suggestion in comments, but you can eliminate one non-terminal (variable), so that it becomes:

      →
      →
      →

      →
      → ε

This says that an input is accepted if and only when it consists of an even number of , followed by either one or one , followed by an even number of .

NB: I used the more common practice to use ε for representing the empty string.

In the more compact regex syntax this would be:

(aa)*[ab](bb)*