How do we know that an NFA has a minimum amount of states?

Question

Is there some kind of proof for this? How can we know that the current NFA has the minimum amount?

Answer 1

As opposed to DFA minimization, where efficient methods exist to not only determine the size of, but actually compute, the smallest DFA in terms of number of states that describes a given regular language, no such general method is known for determining the size of a smallest NFA. Moreover, unless P=PSPACE, no polynomial-time algorithm exists to compute a minimal NFA to recognize a language, as the following decision problem is PSPACE-complete:

Given a DFA M that accepts the regular language L, and an integer k, is there an NFA with ≤ k states accepting L?

(Jiang & Ravikumar 1993).

There is, however, a simple theorem from Glaister and Shallit that can be used to determine lower bounds on the number of states of a minimal NFA:

Let L ⊆ Σ^* be a regular language and suppose that there exist n pairs P = { (x_i, w_i) | 1 ≤ i ≤ n } such that:

1. x_i w_i ∈ L for 1 ≤ i ≤ n
2. x_j w_i ∉ L for 1 ≤ j, i ≤ n and j ≠ i

Then any NFA accepting L has at least n states.

See: Ian Glaister and Jeffrey Shallit (1996). "A lower bound technique for the size of nondeterministic finite automata". Information Processing Letters 59 (2), pp. 75–77. DOI:10.1016/0020-0190(96)00095-6.