确定最小 DFA 将具有多少个状态
这是证明语言不是正则语言的泵引理：如果 L 是正则语言，则存在一个 const N，使得对于 L 中的每个 z，|z|>=N，可以将 z 除以三个子串 (uvw=z)，使得：
1)|uv|<=N;
2)|v|>=1;
3)For each k>=0, uv^kw in L.
N 必须小于或等于接受 L 的 DFA 的最小状态数。因此，要应用泵引理，我需要知道有多少个状态具有最小状态数DFA 接受 L。有没有办法知道有多少个状态会向后？那么有可能在不构建最小 DFA 的情况下知道最小状态数吗？
This is the pumping lemma to demonstare that a language is not regular:If L is a regular language,there is a const N such that, for each z in L, with |z|>=N, is possibile to divide z in three sub-strings (uvw=z)such that:
1)|uv|<=N;
2)|v|>=1;
3)For each k>=0, uv^kw in L.
N must be less or equal than the minumum number of states of the DFA accepting L.So to apply the pumping lemma I need to know how many states will have the minimal DFA accepting L.Is there a way to know how many states will have backwards?So is possibile to know the minimal number of states without building the minimal DFA?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
N 不能小于接受 L 的最小 DFA 中的状态数；否则，DFA 无法接受 L（如果可以的话，接受 L 的 DFA 会小于接受 L 的最小 DFA，这是矛盾的）。我们可以安全地假设 N 等于接受 L 的最小 DFA 中的状态数（此类 DFA 是唯一的）。
严格来说这并不正确。在大多数抽引理证明中，N 实际上是什么并不重要；重要的是 N 是多少。您只需确保目标字符串满足其他属性即可。给定 DFA，可以确定最小 DFA 将具有多少个状态；但是，如果您有 DFA，则无需担心泵引理，因为您已经知道 L 是正则的。事实上，确定 N 使得存在接受 L 的 N 个状态的最小 DFA 构成了所讨论的语言确实是常规语言的有效证明。
通过分析语言的描述并使用 Myhill-Nerode 定理，可以构造语言是正则的证明并找到最小 DFA 中的状态数，而无需实际构建最小 DFA（尽管一旦您完成了使用 Myhill-Nerode 进行这样的证明，构建最小的 DFA 是一个微不足道的练习）。您还可以使用 Myhill-Nerode 作为泵引理的替代方案，通过显示语言的最小 DFA 需要具有无限多个状态（矛盾）来证明语言不规则。
请告诉我这些观察结果是否回答了您的问题；我很乐意提供额外的说明。
N cannot be less than the number of states in a minimal DFA accepting L; otherwise, the DFA couldn't accept L (if it could, you would have a DFA accepting L smaller than the minimal DFA accepting L, a contradiction). We can safely assume that N is equal to the number of states in the minimal DFA accepting L (such DFAs are unique).
This is not strictly true. In most pumping lemma proofs, it doesn't matter what N actually is; you just have to make sure that the target string satisfies the other properties. It is possible, given a DFA, to determine how many states a minimal DFA will have; however, if you have a DFA, there's no need to bother with the pumping lemma, since you already know L is regular. In fact, determining an N such that there's a minimal DFA with N states accepting L constitutes a valid proof that the language in question is indeed regular.
By analyzing the description of the language and using the Myhill-Nerode theorem, it is possible to construct a proof that a language is regular and find the number of states in a minimal DFA, without actually building the minimal DFA (although once you have completed such a proof using Myhill-Nerode, construction of a minimal DFA is a trivial exercise). You can also use Myhill-Nerode as an alternative to the pumping lemma to prove languages aren't regular, by showing a minimal DFA for the language would need to have infinitely many states, a contradiction.
Please let me know whether these observations answer your questions; I will be happy to provide additional clarification.