一个具有挑战性的有限自动机 - 语言是什么？

Question

我有这个有限自动机（FA）并且想编写它的语言。我认为是

L={x E {0,1} | {x with subset of 00 and ends in 1}

，这将有助于了解 FA 的类型。

我认为这是一个DFA，因为每个状态只有一个转换，但接受状态（用双环标记）位于中间而不是末尾。

这是否意味着状态 c 永远不会达到，并且这是否使其既不是 DFA 也不是 NFA？

你觉得怎么样？

Answer 1

该图显示了确定性有限自动机 (DFA) 的状态图。它是确定性的，因为对于给定的输入，没有两种方法可以运行此状态图。

但是接受状态（用双环标记）是在中间而不是在末尾。

没有要求accept状态必须在最后。如果要求所有从接受状态到接受状态的转换都必须是接受状态，那么您只能描述接受有效输入的任何扩展的语言，无论您附加什么内容。 DFA 可以描述一种语言，其中用更多数据扩展有效输入可能会使其无效。例如，{0,1} 上的语言只接受不带零的输入，一旦遇到 0，就会转换到不接受状态。可能存在接受状态，并向外转换到不接受状态。此外，

DFA 上的维基百科页面

也包含此类状态图作为示例。 在你的例子中，状态𝐶是一个

sink

：它是一个你无法逃脱的非接受状态。一旦到达该状态，您就可以断定输入无效。

我认为是

L={x E {0,1} | {x with subset of 00 and ends in 1}

有效输入不必以 1 结尾。如果从状态 𝐴 读取到

0

，我们就会进入 𝐵。如果输入在那里结束（

0

），我们就有了有效的输入。三种状态𝐴、𝐵和𝐶可以描述如下：

𝐴：还没有遇到

0
• 𝐵：恰好遇到了一个
0
• 𝐶：遇到了不止一个
0
因此，这个状态图的语言都是包含一个

0

:

 的所有输入

      𝐿 = {𝑥 ∈ {0,1} | 𝑥 恰好包含一个 0}