Give a regular grammar for L

Question

Give a regular grammar for $L = \{a^n b^n : n \leqslant 100\}$

I would do something like this :

$S \to A \ |\ \text{empty string}$

$A \to aB \ |\ \text{empty string}$

$B \to Ab$

but How do we keep count of the number in the grammar? meaning How does it know when there are more that $100$ $a$'s. Also I'm not even sure if my way makes sense.

Any help would be appreciated.

Answer 1

Hint: Use non-terminals as memory. In particular (and this envisions a right regular grammar) for each $n$ let $A_n$ be a nonterminal which means that (so far) $n$ $\mathtt{a}$'s have been written to the string, and let $B_n$ be a nonterminal which means that $n$ more $\mathtt{b}$'s need to be written to the string.