编译器设计中的有限自动机是什么？

自动机是数字计算机的一种抽象模型，具有离散的输入和输出。每个自动机都包含一个读取输入的机制。可以认为输入是在给定字母表上的字符串，写在自动机可以读取的输入文件上。输入文件被分成称为单元格的较小部分。

它是一种语言的机器或识别器，用于检查语言是否接受该字符串。在**有限自动机**中，**有限**表示有限数量的状态，而自动机表示在没有人工干预的情况下工作的**自动**机器。有限自动机由一组有限状态和从一个状态到另一个状态的转换组成，这些转换出现在从字母表 $\sum$ 中选择的输入符号上。

有限自动机的表示

有两种方法可以表示有限自动机：

• 状态转换图

它是一个具有状态和边的有向图或流程图。

示例

0, 1, 2→States 0 →Initial State 2→Final State a,b→Input Symbols

• 状态转换表

有限自动机可以用 5 元组 (Q,∑,$\delta$,q₀,F) 表示

• Q 是一个有限的非空状态集。
• $\sum$ 是一个有限的输入符号集。
• $\delta$ 是状态转换函数。
• q₀ ∈ Q 是初始状态。
• F $\subseteq$ Q 是终结状态集。

**示例** - 设计一个接受字符串“abb”的有限自动机。

解决方案

状态：Q= {q₀,q₁,q₂,q₃}

输入符号：$\sum$ ={a,b}

状态转换函数 $\delta$: {$\delta$ (q₀,𝑎)=q₁,$\delta$(q₁,𝑏)=q₂,$\delta$(q₂,b)=q₃}

初始状态：q₀

终结状态 (F) : {q3}

有限自动机的类型

有限自动机有两种类型，如下所示：

• 确定性有限自动机 (DFA)

“确定性”意味着对于每个输入，自动机从其当前状态转换到下一个状态只有一个状态。

DFA 可以用 5 元组 (Q,$\sum$,$\delta$,q₀,F) 表示

• Q 是一个有限的非空状态集。
• ∑ 是一个有限的输入符号集。
• $\delta$ 是一个状态转换函数，用于从当前状态移动到下一个状态。

∴ $\delta$:Q x Σ → Q

• q₀ ∈ Q 是初始状态。
• F $\subseteq$ Q 是终结状态集。
• 非确定性有限自动机 (NFA)

“非确定性”意味着可能存在多个可能的转换。因此，对于给定的输入，输出是非确定性的。

NFA 可以用 5 元组 (Q,$\sum$,$\delta$,q₀,F) 表示

• Q 是一个有限的非空状态集。
• ∑ 是一个有限的输入符号集。
• $\delta$ 是一个状态转换函数，用于从当前状态移动到下一个状态。

∴ $\delta$:Q x $\sum$ → 2^Q

• q₀ ∈ Q 是初始状态。
• F $\subseteq$ Q 是终结状态集。

Ginni

更新于： 2021年10月26日

4K+ 次查看

启动您的 职业生涯

通过完成课程获得认证

开始