以图的形式构造确定性有限自动机的规则是什么?我的教授通过示例进行了解释,但我不确定所有图表必须遵循哪些规则。任何帮助表示赞赏,谢谢!
问问题
1964 次
1 回答
5
在我的脑海中,在 DFA 中,这些是主要规则,(特定于 DFA 的术语用双引号括起来):-
对于 DFA 中定义的每个“输入”,每个“状态”都必须有一个“转换”,
这意味着,必须为 DFA 中考虑的每个输入定义一个转换,对于一个状态,以便知道从哪里开始每个输入的那个状态。每个“状态”对于每个“输入”只能有一个“转换”,
这个规则很容易解释,所以如果您已经为特定状态的输入定义了转换,请不要为相同的输入创建另一个转换来自同一个州。
是的,这些是我记得的。希望能帮助到你。此外,这些点可用于区分 dfa 和 nfa。其他简单的绘图规则是:-
建立一个开始状态,用指向该状态的箭头表示
至少有一个最终状态,用同心圆表示以绘制状态边界
将过渡绘制为箭头
用各自的输入符号标记所有转换
于 2011-09-26T03:09:57.543 回答