有限状态机有限状态机|编译器设计

本文概述

DFA
国家发改委

有限状态机用于识别模式。
有限自动机将符号字符串作为输入并相应地更改其状态。在输入中, 找到所需符号后, 就会发生过渡。
过渡期间, 自动机可以移至下一个状态或保持相同状态。
FA具有两种状态：接受状态或拒绝状态。当成功处理输入字符串并且自动机达到其最终状态时, 它将接受。

有限自动机包括以下内容：
Q：状态的有限集合∑：输入符号的有限集合q0：初始状态F：最终状态δ：转移函数
过渡函数可以定义为

δ: Q x ∑ →Q

FA具有两种特征：

DFA（有限自动机）
NDFA（非确定性有限自动机）

DFA DFA代表确定性有限自动机。确定性是指计算的唯一性。在DFA中, 输入字符仅进入一种状态。 DFA不接受null移动, 这意味着DFA在没有任何输入字符的情况下无法更改状态。
DFA具有五个元组{Q, ∑, q0, F, δ}
问：所有状态的集合
∑：输入符号的有限集合, 其中δ：Q x ∑→Q
q0：初始状态
F：最终状态
δ：转移函数
例
请参阅确定性有限自动机的示例：