Equivalent regular grammar with minimum number of nonterminals

Question

Given a set of terminal symbols $\Sigma=\{a,b\}$ and a set of nonterminal symbols $N=\{S,A,B\}$ with start symbol $S$, then the two following sets of production rules are equivalent:

• $S\to aA$
• $A\to aA$
• $A\to bB$
• $B\to aA$
• $B\to bB$
• $B\to \epsilon$

and

• $S\to aA$
• $A\to aA$
• $A\to bA$
• $A\to b$

They both match any string starting with $a$ and ending with $b$, but the second set of rules has only two nonterminals instead of three. Is there a standard way to convert an arbitrary (regular) grammar to the equivalent grammar with the smallest number of non terminals? I don't think this can be achieved by the rules for Chomsky normal form.

Answer 1

A regular grammar corresponds directly to a finite automaton, mapping each non-terminal to a state. So this question is equivalent to asking how to minimize the number states in a finite automaton. Unfortunately, minimizing NFAs is hard. See, for example, Gregor Gamlich, 2007.