grammar - 需要帮助构建确定性有限自动机吗？

Question

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

Answer 1

在我的脑海中，在 DFA 中，这些是主要规则，（特定于 DFA 的术语用双引号括起来）：-

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

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

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

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

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

• 将过渡绘制为箭头
  

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