有限状态机

本文概述

• DFA
• 国家发改委

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

有限自动机包括以下内容：

Q：状态的有限集合∑：输入符号的有限集合q0：初始状态F：最终状态δ：转移函数

过渡函数可以定义为

δ: Q x ∑ →Q

FA具有两种特征：

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

DFA

DFA代表确定性有限自动机。确定性是指计算的唯一性。在DFA中, 输入字符仅进入一种状态。 DFA不接受null移动, 这意味着DFA在没有任何输入字符的情况下无法更改状态。

DFA具有五个元组{Q, ∑, q0, F, δ}

问：所有状态的集合

∑：输入符号的有限集合, 其中δ：Q x ∑→Q

q0：初始状态

F：最终状态

δ：转移函数

例

请参阅确定性有限自动机的示例：

Q = {q0, q1, q2}
∑ = {0, 1}
q0 = {q0}
F = {q3}

国家发改委

NDFA是指非确定性有限自动机。它用于为特定输入转换任何数量的状态。 NDFA接受NULL动作, 这意味着它可以更改状态而无需读取符号。

NDFA还具有与DFA相同的五个州。但是NDFA具有不同的过渡功能。

NDFA的转换函数可以定义为：

	δ: Q x ∑ →2Q

例

请参阅非确定性有限自动机的示例：

Q = {q0, q1, q2}
∑ = {0, 1}
q0 = {q0}
F = {q3}