我正在尝试证明这个 DFA 对于这个联盟来说是最小的。
最佳答案
您可以通过证明每个状态都是可达且可区分的来证明您的 DFA 是最小的。
证明一个状态st是可达的，你必须给出一个从起始状态(图中的 q0)到状态 st 的词(一个可能为空的符号序列) .因此，对于您的图表，您必须给出六个单词:一个代表 q0 , q1 , q2 , q3 , q4 , 和 X .我会让你开始:
<表类="s-表">
<头>
状态
从
<正文>
""(空词)
(读者练习)
(读者练习)
(读者练习)
q0到达它的单词q0 q1 a q2 ab q3 q4 X 证明两种状态s1和 s2是可区分的，你必须给出一个来自 s1 的词到接受状态，从s2到拒绝状态，反之亦然。所以对于你的图表，你需要提供 6 choose 2 = 15 words: one to distinctive q0来自 q1 , 和一个区分q0来自 q2 , 和一个区分q1来自 q2 ， 等等。例如，单词 a区分q0来自 q3 ，因为 a来自 q0至 q1 (拒绝状态)，但是 a来自 q3至 q4 (接受状态)。
我会让你开始:
<表类="s-表">
<头>
状态1
状态2
区分国家的词
<正文>
""(空字符串)
(读者练习)
(读者练习)
(读者练习)
(读者练习)
(读者练习)
(读者练习)
(给读者的练习，但你找不到)
(读者练习)
(读者练习)
(读者练习)
(读者练习)
q0 q1 b q0 q2 q0 q3 a q0 q4 ba q0 X q1 q2 q1 q3 q1 q4 q1 X q2 q3 q2 q4 q2 X q3 q4 q3 X q4 X 关于computer-science - 我如何证明这个 dFa 是最小的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69273747/