0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.