输入遵循确定性有限自动机接受的语言的描述

Question

我尝试将其最小化，但没有帮助，因此这是DFA欺骗了我的头脑：

这里有一些被拒绝的字符串，但我没有从中提出解决方案...

1，00，000，001，010，100，0000，0001，0010，0100，1000，00000，00001，00010，00100，01000，10000

Answer 1

对于这样的问题，在DFA中有很多接受状态，通常最好考虑一下DFA rejects是什么字符串，而不是它接受的字符串。

在这种情况下，仅状态q2和q4被拒绝，并且由拒绝描述的语言更为简单。要达到q2，您需要000*。要进入第4季度，您需要000*10*或0100*或1000*。

因此被拒绝的字符串是至少具有2个0，最多具有一个1。

Ergo，可接受的字符串是具有两个或多个1或最多具有一个0的字符串。请注意，此描述涵盖了空字符串和短字符串，例如1，0，01，10和11（它们最多具有一个0）。