【13.9.2】DFA

DFA 即为确定的有穷状体自动机,和文法不同,文法注重描述一个串是如何产生的。而 DFA 则注重于观察该串是否能被某些文法接收。

通过五元组:

M=(状态集合, 输入字母表, 转移函数, 起始状态, 接收状态集合)

来描述一个 DFA。其中落入接收状态的串是能够被 DFA 识别的。比如:

此外,DFA 还应该有陷阱状态,表示当前串无法被接收时,状态就落入陷阱状态。比如有如下的例子,qt 就是陷阱状态,表示读取到不被接受的串:

通过【即时描述】来表达一个自动机接收某个串的过程。即时描述通过状态 q 在串上不停滑动,生动地表示了接收的过程,如下图:

参考资料

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学