术语“自动机”源自希腊语单词“αὐτόματα”，意思是“自作用”。自动机（复数形式为 Automata）是一种抽象的自驱动计算设备，它自动执行预定的操作序列。

具有有限状态数的自动机称为 Finite Automaton (FA) 或 Finite State Machine (FSM)。

在 DFA 中，对于每个输入符号，都可以确定机器将移动到的状态。因此，它被称为 Deterministic Automaton 。由于它具有有限数量的状态，因此机器被称为 Deterministic Finite Machine 或 Deterministic Finite Automaton. 。

DFA 可以表示为 5 元组 (Q, ∑, δ, q0, F)，其中 −

DFA 由称为 state diagram 的有向图表示。

NDFA 可以用 5 元组 (Q, ∑, δ, q0, F) 表示，其中−

NDFA 由称为状态图的有向图表示。

Example

令非确定性有限自动机为→

过渡函数 δ 如下所示−

它的图形表示如下−

下表列出了 DFA 和 NDFA 之间的差异。

当 DFA/NDFA 从初始状态开始在完整读取字符串后结束于接受状态（任何最终状态）时，一个字符串才会被 DFA/NDFA 接受。

字符串 S 被 DFA/NDFA (Q, ∑, δ, q0, F) 接受，当且仅当

δ (q0, S) ∈ F*

DFA/NDFA 接受的语言 L 是

{S | S ∈ ∑ 并且 δ*(q0, S) ∈ F}*

如果一个字符串 S′ 不被 DFA/NDFA (Q, ∑, δ, q0, F) 所接受，则

δ (q0, S′) ∉ F*

DFA/NDFA 所不接受的语言 L′（所接受语言 L 的补集）为

{S | S ∈ ∑ and δ*(q0, S) ∉ F}*

Example

我们考虑图 1.3 中所示的 DFA。可以从 DFA 推导出可接受的字符串。

上述 DFA 所接受的字符串：{0, 00, 11, 010, 101, …​…​…​..}

上述 DFA 所不接受的字符串：{1, 011, 111, …​…​..}

设 X = (Qx, ∑, δx, q0, Fx) 是接受语言 L(X) 的 NDFA。我们必须设计一个等效 DFA Y = (Qy, ∑, δy, q0, Fy) ，使得 L(Y) = L(X) 。以下过程将 NDFA 转换为其等效 DFA −

Input − NDFA

Output − 等效 DFA

Step 1 − 根据给定的 NDFA 创建状态表。

Step 2 − 根据等效 DFA 的可能的输入字母创建一个空白状态表。

Step 3 − 标记为 q0 的 DFA 的起始状态（与 NDFA 相同）。

Step 4 − 找出对于每个可能的输入字母的状态 {Q0, Q1,…​ , Qn} 的组合。

Step 5 − 每次在输入字母列中生成一个新的 DFA 状态时，我们都必须重新应用步骤 4，否则转到步骤 6。

Step 6 − 包含 NDFA 的任何最终状态的状态是等效 DFA 的最终状态。

我们考虑下图所示的 NDFA。

使用上述算法，我们可以找到其等效 DFA。DFA 的状态表如下所示。

DFA 的状态图如下所示 −

如果X和Y是DFA中的两个状态，如果它们不可区分，我们可以将这两个状态组合成{X，Y}。如果存在至少一个字符串S，则两个状态是可以区分的，即δ（X，S）和δ（Y，S）中的一个被接受，另一个不被接受。因此，当且仅当所有状态都可区分时，DFA才是最小的。

Mealy 机是一种 FSM，其输出取决于当前状态以及当前输入。

它可以用 6 元组 (Q，∑，O，δ，X，q0) 来描述，其中 -

Mealy 机的状态表如下所示 -

上述 Mealy 机的状态图如下 -

Moore 机是一种 FSM，其输出仅取决于当前状态。

摩尔机可以用 6 元组 (Q, ∑, O, δ, X, q0) 来描述，其中 -

摩尔机的状态表如下所示 -

上述 Moore 机的状态图是 −

下表重点介绍了 Mealy 机与 Moore 机之间的不同点。

语法 G 可以形式化为一个 4 元组 (N、T、S、P)，其中 −

字符串可以用语法中的产生式从其他字符串中派生。如果语法 G 有产生式 α → β ，我们可以说 x α y 在 G 中派生出 x β y 。此派生表示为 −

x α y ⇒G x β y

如果存在一个语法

G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}

此处 S 产生 AB ，我们可以用 a 替换 A ，用 b 替换 B 。这里，唯一可接受的字符串是 ab ，即

L(G) = {ab}

假设我们有以下语法 −

G：N = {S、A、B} T = {a、b} P = {S → AB，A → aA|a，B → bB|b}

此语法生成的语言 −

L(G) = {ab、a2b、ab2、a2b2、………}

q4 生成正则语言。Type-3 语法必须在左侧有一个非终结符，在右侧有一个终结符或一个终结符后跟一个非终结符。

产生式必须采用以下形式 Type-3 grammars

其中 X → a or X → aY （非终结符）

和 X, Y ∈ N （终结符）

规则 a ∈ T 被允许，如果 S → ε 不出现在任何规则的右侧。

Type-2 grammars 生成上下文无关语言。

产生式应为 A → γ 形式

其中*A ∈ N*（非终结符）

和 γ ∈ (T ∪ N) *（终结符和非终结符串）。

由这些语法生成的这些语言可被非确定性下推自动机识别。

Type-1 grammars 生成上下文相关语言。产生式应为

α A β → α γ β

其中 A ∈ N （非终结符）

和 α, β, γ ∈ (T ∪ N) *（终结符和非终结符串）。

字符串 α 和 β 可为空，但 γ 必须非空。

如果 S 未出现在任何规则的右侧，则规则 S → ε 是允许的。由这些语法生成的语言被线性有界自动机所识别。

Type-0 grammars 递归生成可枚举的语言。产生式没有任何限制。它们是包括所有形式文法的任意相结构语法。

它们生成被图灵机识别的语言。

产生式可以 α → β 的形式出现，其中 α 是至少有一个非终结符的终结符和非终结符字符串，而 α 不能为 null。 β 是终结符和非终结符字符串。

Property 1 . 两个正则集的并集是正则。

Proof −

让我们取两个正则表达式

RE1 = a(aa)，RE2 = (aa)

所以，L1 = {a, aaa, aaaaa,…​..}（不包括 Null 的奇数长度字符串）

且 L2 ={ ε, aa, aaaa, aaaaaa,…​…​.} （包括 Null 的偶数长度字符串）

L1 ∪ L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,…​…​.}

（包括 Null 的所有可能长度的字符串）

RE (L1 ∪ L2) = a* （本身就是一个正则表达式）

Hence, proved.

Property 2. 两个正则集的交集是正则。

Proof −

让我们取两个正则表达式

RE1 = a(a*)，RE2 = (aa)*

所以，L1 = { a,aa, aaa, aaaa, …​.} （不包括 Null 的所有可能长度字符串）

L2 = { ε, aa, aaaa, aaaaaa,…}（包含空字符串的偶数长度字符串）

L1 ∩ L2 = { aa, aaaa, aaaaaa,…}（不包含空字符串的偶数长度字符串）

RE (L1 ∩ L2) = aa(aa)*，本身是一个正则表达式。

Hence, proved.

Property 3. 一个正则集合的补集是正则的。

Proof −

我们取正则表达式−

RE = (aa)*

所以，L = {ε, aa, aaaa, aaaaaa, …}（包含空字符串的偶数长度字符串）

L 的补集是不在 L 中的所有字符串。

所以，L’ = {a, aaa, aaaaa, …}（不包含空字符串的奇数长度字符串）

RE (L’) = a(aa)*，本身是一个正则表达式。

Hence, proved.

Property 4. 两个正则集合的差是正则的。

Proof −

我们取两个正则表达式−

RE1 = a (a*) 和 RE2 = (aa)*

所以，L1 = {a, aa, aaa, aaaa, …}（包含所有可能的长度且不包含空字符串的字符串）

L2 = { ε, aa, aaaa, aaaaaa,…}（包含空字符串的偶数长度字符串）

L1 – L2 = {a, aaa, aaaaa, aaaaaaa, …}

（不包含空字符串的所有奇数长度字符串）

RE (L1 – L2) = a (aa)*，是一个正则表达式。

Hence, proved.

Property 5. 一个正则集合的反转是正则的。

Proof −

我们要证明 LR 也是正则的，如果 L 是一个正则集合。

令 L = {01，10，11，10}

RE (L) = 01 + 10 + 11 + 10

LR = {10，01，11，01}

RE (LR) = 01 + 10 + 11 + 10 为正则语言

Hence, proved.

Property 6. 正则集合的闭包为正则语言。

Proof −

如果 L = {a, aaa, aaaaa, …​…​.} （长度为奇数且不含空集合的字符串），

即 RE (L) = a (aa)*

L* = {a, aa, aaa, aaaa , aaaaa,……………} （长度可为任意正整数且不含空集合的字符串）

RE (L*) = a (a)*

Hence, proved.

Property 7. 两个正则集合的连接为正则语言。

Proof −

令 RE1 = (0+1) 0 and RE2 = 01(0+1)

此处，L1 = {0, 00, 10, 000, 010, …​…​} （以 0 结尾的字符串集合）

且 L2 = {01, 010,011,…​..} （以 01 开头的字符串集合）

则 L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,…​…​…​…​.}

包含 001 作为子串的字符串集合，可以用正则表达式表示为 − (0 + 1) 001(0 + 1)

因此得证。

给出正则表达式 R, P, L, Q，则有如下恒等式：

Step 1 根据给定的正则表达式构建一个带有空动作的 NFA。

Step 2 从 NFA 中删除空转换，并将其转换成等效的 DFA。

Problem

将以下 RA 转换成等效的 DFA − 1 (0 + 1)* 0

Solution

我们将三个表达式“1”、“(0 + 1)*”和“0”连接在一起

现在我们将删除 ε 转换。从 NDFA 中删除 ε 转换后，我们得到以下结果 −

它是与 RE − 1 (0 + 1)* 0 相对应的 NDFA。如果你想将其转换成 DFA，只需应用第 1 章中讨论的 NDFA 到 DFA 的转换方法。

带有空动作的有限自动机 (FA-ε) 不仅在从字母集合提供输入后进行转换，还可以在没有输入符号的情况下进行转换。这种没有输入的转换称为 null move 。

NFA-ε 由一个 5 元组（Q、∑、δ、q0、F）正式表示，其中包括

上述 (FA-ε) 接受一个字符串集合 − {0, 1, 01}

如果在 NDFA 中，存在从顶点 X 到顶点 Y 的 ϵ 动作，我们可以使用以下步骤将其删除 −

Problem

将以下 NFA-ε 转换为没有空移动的 NFA。

Solution

Step 1 -

这里 ε 转换在 q1 和 q2 之间，所以让 q1 等于 X ，而 qf 等于 Y 。

这里从 qf 出发到 qf 的输出边针对输入 0 和 1。

Step 2 -

现在，我们将从 q1 复制所有这些边，而不会更改从 qf 分出的边，并获得以下 FA −

Step 3 -

这里 q1 是一个初始状态，所以我们也将 qf 设置为初始状态。

因此 FA 变成 −

Step 4 -

这里 qf 是一个终止状态，因此我们也将 q1 设置为终止状态。

因此 FA 变成 −

设 L 是正则语言。那么存在常量 ‘c’ 使得对于 L 中的每个字符串 w −

|w| ≥ c

我们可以把 w 分成三个字符串 w = xyz ，使得 −

抽取引理用于证明某些语言不是正则的。它不应该被用来证明语言是正则的。

Hence L is not regular.

Problem

证明 L = {aibi | i ≥ 0} 不是正则的。

Solution −

导出树或解析树是有序的根树，可以直观地表示从上下文无关文法导出的字符串的语义信息。

在一个上下文无关文法中 G ，如果有一个形式为 X → Xa 的产生式，其中 X 是一个非终结符， ‘a’ 是一个终结符字符串，它被称为 left recursive production 。具有左递归产生式的文法称为 left recursive grammar 。

而如果在一个上下文无关文法中 G ，如果有一个形式为 X → aX 的产生式，其中 X 是一个非终结符， ‘a’ 是一个终结符字符串，它被称为 right recursive production 。具有右递归产生式的文法称为 right recursive grammar 。

检查产生规则为 −

X → X+X | X*X |X| a

的文法 G 是否模糊。

让我们找出字符串“a+a*a”的派生树。它有两个最左派生。

Derivation 1 −X → X+X → a X → a X*X → a+a*X → a+a*a

Parse tree 1 −

Derivation 2 − X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

Parse tree 2 −

由于对于单个字符串“a+a*a”有两个解析树，文法 G 是模糊的。

设 L1 和 L2 为两种无上下文语言。则 L1 ∪ L2 也是无上下文的。

如果 L1 和 L2 是无上下文语言，则 L1L2 也是无上下文的。

若 L 是上下文无关语言，那么 L* 也是上下文无关语言。

CFG 分为两个阶段来简化 −

Phase 1 − 从 CFG G 推导出一个等价文法 G’ ，使得每个变量都推导出某个终结符字符串。

Derivation Procedure −

步骤 1 − 包含所有推导出某个终结符的符号 W1 ，并初始化 i=1 。

步骤 2 − 包含所有推导出 Wi 的符号 Wi+1 。

步骤 3 − 增加 i 并重复步骤 2，直到 Wi+1 = Wi 。

步骤 4 − 包含所有包含 Wi 的产生式。

Phase 2 − 从 CFG G’ 推导出一个等价文法 G” ，使得每个符号都出现在句式中。

Derivation Procedure −

步骤 1 − 将起始符号包含在 Y1 中，并初始化 i = 1 。

步骤 2 − 包含所有可以从 Yi 推导出的符号 Yi+1 ，并包含所有已经应用的产生式。

步骤 3 − 增加 i 并重复步骤 2，直到 Yi+1 = Yi 。

任何形式为 A → B 的产生式，其中 A, B ∈ 非终结符被称作 unit production. 。

在 CFG 中，非终结符 ‘A’ 是一个空值变量，如果存在产生式 A → ε 或存在从 A 开始最终以

ε: A → …​…​.… → ε

Step 1 − 如果起始符号 S 出现在某个右侧，创建一个新的起始符号 S’ 和一个新的产生式 S’→ S 。

Step 2 − 删除空产生式。（使用前面讨论的空产生式消除算法）

Step 3 − 删除单位产生式。（使用前面讨论的单位产生式消除算法）

Step 4 − 替换每个将 n > 2 替换成 A → B1C 产生的 A → B1…Bn ，将 C → B2 …Bn 替换成 A → B1C 。对右侧有两个或更多符号的每个产生式重复此步骤。

Step 5 − 如果任何产生式的右侧形式为 A → aB ，其中 a 是一个终结符且 A, B 是非终结符，那么该产生式被替换为 A → XB 和 X → a 。对形式为 A → aB 的每个产生式重复此步骤。

Step 1 − 如果起始符号 S 出现于某个右侧，创建一个新起始符号 S’ 和一个新产生式 S’ → S 。

Step 2 − 删除空产生式。（使用前面讨论的空产生式消除算法）

Step 3 − 删除单位产生式。（使用前面讨论的单位产生式消除算法）

Step 4 − 删除所有直接和间接左递归。

Step 5 − 适当替换产生式以将其转换为 GNF 的正确形式。

如果 L 是上下文无关语言，那么存在一个泵长 p ，使得任何长度为 ≥ p 的字符串 w ∈ L 均可写为 w = uvxyz ，其中 vy ≠ ε 、 |vxy| ≤ p ，且对于所有 i ≥ 0, uvixyiz ∈ L 。

泵引理用于检查语法是否上下文无关。让我们举一个例子来说明它是如何检查的。

下推自动机是一种以与我们为正规语法设计DFA类似的方式实现无上下文语法的途径。一个DFA可以记忆有限量的信息，而一个PDA可以记忆无限量的信息。

基本上，下推自动机为 −

"Finite state machine" + "a stack"

一个下推自动机有三个组件 −

栈头扫描栈的顶端符号。

栈执行两种操作 −

一个PDA可以读取或不读取一个输入符号，但它必须在每个转换中读取栈的顶部。

PDA 可以形式化描述为一个 7 元组 (Q, ∑, S, δ, q0, I, F)

下图展示了一个 PDA 从一个状态 q1 到状态 q2 的转换，标记为 a,b → c

这意味着在状态 q1 ，如果我们遇到一个输入字符串 ‘a’ 且栈顶符号是 ‘b’ ，则我们弹出 ‘b’ ，入栈 ‘c’ 至栈顶，并移至状态 q2 。

在最终状态可接受性中，当读取完整个字符串后，如果 PDA 处于最终状态，则 PDA 接受一个字符串。从开始状态，我们可以采取最终停留在最终状态的步骤，而无论栈值是什么。只要我们最终处于最终状态，那么栈值就无关紧要。

对于 PDA (Q, ∑, S, δ, q0, I, F)，结束状态 F 集合接受的语言为 −

L(PDA) = {w | (q0, w, I) ⊢* (q, ε, x), q ∈ F}

对于任何输入的栈字符串 x 。

此处 PDA 在读取完整个字符串后，如果 PDA 清空了栈，则接受一个字符串。

对于 PDA (Q, ∑, S, δ, q0, I, F)，空栈接受的语言为 −

L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}

Input - 一个 CFG，G = (V, T, P, S)

Output − 等价的 PDA，P = (Q, ∑, S, δ, q0, I, F)

Step 1 − 将 CFG 的产生式转换成 GNF。

Step 2 − PDA 将只有唯一状态 {q}。

Step 3 − CFG 的起始符号将是 PDA 中的起始符号。

Step 4 − CFG的所有非终结符号将是 PDA 的栈符号，且 CFG 的所有终结符号将是 PDA 的输入符号。

Step 5 − 对于形式 A → aX 的每个产生式，其中 a 为终结符， A, X 是终结符和非终结符的组合，创建转换 δ (q, a, A) 。

Input - 一个 CFG，G = (V, T, P, S)

Output − 等价的 PDA，P = (Q, ∑, S, δ, q0, I, F)，其中语法 G 的非终结符为 {Xwx | w,x ∈ Q}，开始状态为 Aq0,F。

Step 1 − 对于 Q 中的每个 w、x、y、z，S 中的 m 以及 ∑ 中的 a、b，如果 δ (w, a, ε) 包含 (y, m) 且 (z, b, m) 包含 (x, ε) ，则在语法 G 中添加产生式规则 Xwx → a Xyzb。

Step 2 - 对于任意 Q 中的 w、x、y、z，在语法 G 中添加产生式 Xwx → XwyXyx。

Step 3 - 对于 Q 中的 w，在语法 G 中添加产生式 Xww → ε。

对于自顶向下解析，PDA 有以下四种类型的转换 -

对于自底向上解析，PDA 具有以下四种类型的转换 -

图灵机 ™ 是一种数学模型，它由一条分成小格子的无限长胶带组成，输入内容写在胶带上。它包含一个用来读取输入胶带磁头的。状态寄存器存储图灵机的状态。在读取输入符号之后，它会用其他符号替换该符号，改变其内部状态，并向右或向左移动一个单元格。如果 TM 达到最终状态，则接受输入字符串，否则拒绝。

TM 可以形式上描述为一个 7 元组 (Q，X，∑，δ，q0，B，F)，其中 −

对于图灵机，时间复杂度指代机器针对某些输入符号初始化时，磁带移动次数的度量，空间复杂度是指磁带上书写单元格的数量。

时间复杂度所有合理函数 −

T(n) = O(n log n)

TM 的空间复杂性 −

S(n) = O(n)

下面已借助几个示例说明了设计图灵机的基本准则。

找出以下问题是否可判定的 −

数字“m”是否为素数？

给定正则语言 L 和字符串 w ，我们如何检查是否 w ∈ L ？

如果 P 是一个非平凡属性而语言持有属性，Lp，由图灵机 M 识别，则 Lp = {<M> | L(M) ∈ P} 是不可判定的。

假设一个属性P为非平凡的且 φ ∈ P。

由于P为非平凡的，所以至少有一门语言满足P，即L(M0) ∈ P，此图灵机为M0。

不妨设w是一个特定时刻的输入，N是一台图灵机，它遵循−

由输入x

一个函数将一个实例ATM = {<M,w>| M接受输入w}映射到一个N，使得

由于ATM是不可判定性的，并且它可以简化为Lp，因此Lp也是不可判定性的。

找出列表

M = (abb, aa, aaa) 和 N = (bba, aaa, aa)

是否有后缀对应解？

找出列表 M = (ab, bab, bbaaa) 和 N = (a, ba, bab) 是否有后缀对应解？