nfa - 我们如何知道 NFA 有最少的状态？

Question

有什么证据可以证明这一点吗？我们怎么知道当前的 NFA 有最小的量呢？

Answer 1

与DFA 最小化相反，存在有效的方法来不仅确定，而且实际计算描述给定常规语言的状态数量的最小 DFA，没有这样的通用方法用于确定最小的 NFA。此外，除非 P= PSPACE，否则不存在多项式时间算法来计算最小 NFA 来识别语言，因为以下决策问题是PSPACE 完备的：

给定一个接受常规语言L的 DFA M和一个整数k，是否存在一个具有 ≤ k个状态的 NFA 接受L？

(Jiang & Ravikumar 1993)。

然而，来自 Glaister 和 Shallit 的一个简单定理可用于确定最小 NFA 状态数的下限：

令L ⊆ Σ ^*为正则语言并假设存在n对P = { ( x _i , w _i ) | 1 ≤ i ≤ n } 使得：

1. x _i w _i ∈ L对于 1 ≤ i ≤ n
2. x _j w _i ∉ L对于 1 ≤ j , i ≤ n且j ≠ i

那么任何接受L的NFA至少有n个状态。

参见：Ian Glaister 和 Jeffrey Shallit (1996)。“非确定性有限自动机大小的下界技术”。信息处理快报 59 (2)，第 75-77 页。DOI：10.1016/0020-0190(96)00095-6。