nfa - 我们怎么知道 NFA 有最少的状态？

Question

这有什么证据吗？我们怎么知道当前NFA有最小量？

Answer 1

相对于DFA minimization ，其中存在有效的方法不仅可以根据描述给定常规语言的状态数确定最小 DFA 的大小，而且可以实际计算最小 DFA 的大小，但尚无用于确定最小 NFA 大小的通用方法。此外，除非 P= PSPACE , 不存在计算最小 NFA 来识别语言的多项式时间算法，因为以下决策问题是 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)。

然而，有一个来自 Glaister 和 Shallit 的简单定理可用于确定最小 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.

参见:Ian Glaister 和 Jeffrey Shallit (1996)。 “A lower bound technique for the size of nondeterministic finite automata”。 信息处理快报 59 (2)，第 75–77 页。 DOI:10.1016/0020-0190(96)00095-6 .