# Equivalent regular grammar with minimum number of nonterminals

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.

## 1 Answer

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.