1

我试图掌握绘制 DFA 的窍门。我的以下尝试有以下问题，想知道是否有人可以告诉我我是否正确，或者如果不正确，我做错了什么。谢谢！此外，如果有人有很好的资源来了解有关如何执行这些操作的更多信息，将不胜感激。

给出识别下列语言的 DFA 的状态图。在所有部分中，字母表都是 {0,1 }

{w | w 的长度最多为 5}

在此处输入图像描述

4

3 回答 3

1

这里有一些线索。

  • “最多 5 个”：这意味着您必须进行一些计数。在状态机中，计数是通过每个节点的上下文来完成的。换句话说，您将需要许多节点，每个节点都有一个特殊的含义，而那个含义就是您的“计数器值”。
  • “最多 5 个”：这意味着您必须接受长度为 0、1、2、3、4 和 5 的单词。（所有这些都有唯一值，提示提示。）
  • 您的字母表是，但对频率、顺序或任何与and{0,1}相关的语言没有要求。这意味着每次有 的转换时，相同的转换必须可用于，反之亦然。（或者一些等价的关系可以简化为这条规则——但这在括号中，因为这不是你需要考虑的事情。）0101
于 2011-09-20T01:24:30.097 回答
0

我认为上面显示的 DFA 是错误的。它将接受长度为 5 的字符串，因此您应该将所有前六个状态设为最终状态。你只接受'1'，但它也应该接受'0'......所以将0与所有1连接起来。

于 2011-09-20T01:25:17.597 回答
0

这是您的错误：

  • 您没有标记的开始状态。
  • 字符串“0”、“”（空字符串）、“1”被拒绝，但在规定的语言范围内。换句话说，您只接受长度正好为 5 的单词，而不是所有长度为 5 或更短的单词。

由于字母表是 {0, 1}，因此您必须在每个状态中指定遇到 0 或 1 时会发生什么。如果您遇到未指定边的输入字符，按照惯例，您将进入死状态，该状态始终返回自身并且永远不会被接受，但未绘制。这就是为什么你的最右边的状态是不必要的，但你的左边的状态是不完整的。

最终的大提示：您可以有多个“接受”或“最终”状态。

于 2011-09-20T01:25:27.490 回答