确定的有穷自动机 DFA

定义

• DFA 的定义

状态转移图

1. 每个$q$对应一个节点，用圆圈表示
2. 状态转悠$\delta(q,a)=p$为一条从$q$到$p$而且标记为输入字符$a$的有向边
3. 开始状态$q_0$用一个标有 start 的箭头表示
4. 接受状态的节点，用双圆圈表示

状态转移表

1. 每个状态$q$对应一行，每个输入字符对应一列
2. $\delta(q,a)=p$表示为用第$q$行第$a$列填入$p$
3. 开始状态$q_0$前用箭头$\rightarrow$表示
4. 接受状态$q\in F$前用$*$表示

例子

• 设计一个 DFA，在任何由0和1构成的串中，接受含有01子串的全部串。
• $\Sigma=\{0,1\}$，DFA：接受全部以1结尾的
• $\Sigma=\{0,1\}$，DFA：接受$\Sigma^*$