1

以图的形式构造确定性有限自动机的规则是什么?我的教授通过示例进行了解释,但我不确定所有图表必须遵循哪些规则。任何帮助表示赞赏,谢谢!

4

1 回答 1

5

在我的脑海中,在 DFA 中,这些是主要规则,(特定于 DFA 的术语用双引号括起来):-

  • 对于 DFA 中定义的每个“输入”,每个“状态”都必须有一个“转换”,
    这意味着,必须为 DFA 中考虑的每个输入定义一个转换,对于一个状态,以便知道从哪里开始每个输入的那个状态。

  • 每个“状态”对于每个“输入”只能有一个“转换”,
    这个规则很容易解释,所以如果您已经为特定状态的输入定义了转换,请不要为相同的输入创建另一个转换来自同一个州。

是的,这些是我记得的。希望能帮助到你。此外,这些点可用于区分 dfa 和 nfa。其他简单的绘图规则是:-

  • 建立一个开始状态,用指向该状态的箭头表示

  • 至少有一个最终状态,用同心圆表示以绘制状态边界

  • 将过渡绘制为箭头

  • 用各自的输入符号标记所有转换

于 2011-09-26T03:09:57.543 回答