计算理论初步——形式语言与自动机

形式语言入门

一、字符串理论

1.理论模型：

A A A是一个有限字母集，我们定义 A A A上的串结构：
空串：没有任何字母的串 λ \lambda λ是 A A A上的串，
单个字符的串：对于 A A A中的任意字母 a a a是 A A A上的串，
加法（拼接）：对于 A A A上任意两个字符串 s s s和 t t t， s + t s+t s+t也是 A A A中的字符串，
模：所有的串都有有限的长度，由空串 λ \lambda λ每次添加一个 A A A中的字符得到串 s s s所进行的加法次数称为串 s s s的长度，空串的长度为0，
偏序结构：对于 A A A上的串 δ \delta δ和 θ \theta θ，如果存在 A A A上的串 α , ω \alpha,\omega α,ω使得 δ = α + θ + ω \delta=\alpha+\theta+\omega δ=α+θ+ω，则称 θ \theta θ是 δ \delta δ的子串，记作 δ ≥ θ \delta \geq \theta δ≥θ，
子串的替换：对于 A A A上的串 s s s和 t t t，如果 s ≥ t s\geq t s≥t，对于任意 A A A上的串 c c c， s : t → c s:t\to c s:t→c也是 A A A上的串.特别的，当 c c c是空串时，记作 s − t s-t s−t.

我们记 A ∗ A^* A∗为字母集 A A A上所有的串构成的集合，显然 A ∗ A^* A∗是可数集。
注1：加法不满足交换律，并且 A ∗ A^* A∗对无限次加法不一定封闭（无限次加空串是封闭的）

2.串的性质：

串的运算之间的关系：

1. 加法和模的关系： ∣ a + c ∣ ≥ ∣ a ∣ |a+c|\geq|a| ∣a+c∣≥∣a∣， ∣ c + a ∣ ≥ ∣ a ∣ |c+a|\geq|a| ∣c+a∣≥∣a∣， ∣ a + c ∣ = ∣ a ∣ + ∣ c ∣ |a+c|=|a|+|c| ∣a+c∣=∣a∣+∣c∣,
2. 加法和偏序的关系：如果 a ≥ b a\geq b a≥b，那么 a + c ≥ b a+c \geq b a+c≥b， c + a ≥ b c+a \geq b c+a≥b，
3. 偏序和模的关系：如果 a ≥ c a \geq c a≥c，那么 ∣ a ∣ ≥ ∣ c ∣ |a| \geq |c| ∣a∣≥∣c∣,
4. 替换和加法的关系：令 s = j + t + k s=j+t+k s=j+t+k， s : t → c s:t \to c s:t→c， s = j + c + k s=j+c+k s=j+c+k.

字符串集上的运算：

1. A + = A ∗ − { λ } A^+=A^* - \{\lambda\} A+=A∗−{λ}
2. 加法： L 1 + L 2 = { x + y ∣ x ∈ L 1 , y ∈ L 2 } L^1+L^2=\{x+y|x\in L^1,y\in L^2\} L1+L2={x+y∣x∈L1,y∈L2}
3. n L = ∑ i = 1 n L ,   0 L = { λ } nL=\sum_{i=1}^{n}L,\ 0L=\{\lambda\} nL=∑i=1n​L, 0L={λ}
4. 闭包： L ∗ = ∑ i = 0 n i L ,   L + = ∑ i = 1 n i L L^*=\sum_{i=0}^niL,\ L^+=\sum_{i=1}^niL L∗=∑i=0n​iL, L+=∑i=1n​iL

二、文法

1.理论模型：

一个短语结构文法 G G G是一个四元组 ( A ∗ , T , S , P ) (A^*,T,S,P) (A∗,T,S,P)，其中 A ∗ A^* A∗是字母表 A A A生成的所有串的集合， T T T是 A ∗ A^* A∗的子集， S S S是 A ∗ A^* A∗的一个元素， P P P是一系列替换规则。

1. T T T中的元素不可被替换，称作 G G G的终结符，
2. S S S是 G G G的初始符，一个短语结构必须从 S S S开始生成，
3. P P P是 G G G的产生式集，是 A ∗ A^* A∗上替换的集合，
4. 短语的派生： ω 0 = l + z 0 + r \omega_0=l+z_0+r ω0​=l+z0​+r， z 0 → z 1 z_0 \to z_1 z0​→z1​是一个产生式，称 ω 1 \omega_1 ω1​是 ω 0 \omega_0 ω0​的派生，记作 ω 0 → ω 1 \omega_0 \rightarrow \omega_1 ω0​→ω1​.
   注： S S S不能在任何产生式的右边

设 G = ( A ∗ , T , S , P ) G=(A^*,T,S,P) G=(A∗,T,S,P)是一个文法，由 G G G生成的语言是初始符 S S S能够派生的所有终结符串构成的集合，记作 L ( G ) = { ω ∈ A ∗ ∣ S → ω } L(G)=\{\omega\in A^*|S\to\omega\} L(G)={ω∈A∗∣S→ω}

2.文法类型

1. 0型：对产生式没有规则限制
2. 1型：只有 ω 1 = l A r → l ω 1 r \omega_1 = lAr \to l\omega_1 r ω1​=lAr→lω1​r，和 S → λ S\to\lambda S→λ两种替换规则的文法
3. 2型（上下文无关文法）：只有 ω 1 → ω 2 \omega_1 \to \omega_2 ω1​→ω2​的替换规则， ω 1 \omega_1 ω1​是单个非终结符串
4. 3型：只有 ω 1 → ω 2 \omega_1 \to \omega_2 ω1​→ω2​的替换规则， ( ( ω 1 = A ) ∧ ( ( ω 2 = a B ) ∨ ( ω 2 = a ) ) ) ∨ ( ( ω 1 = S ) ∧ ( ω 2 = λ ) ) ((\omega_1=A )\wedge((\omega_2=aB )\vee(\omega_2=a)))\vee((\omega_1=S)\wedge(\omega_2=\lambda)) ((ω1​=A)∧((ω2​=aB)∨(ω2​=a)))∨((ω1​=S)∧(ω2​=λ))

单调性：在产生式 ω 1 → ω 2 \omega_1 \to \omega_2 ω1​→ω2​中，如果 ∣ ω 1 ∣ ≤ ∣ ω 2 ∣ |\omega_1|\leq|\omega_2| ∣ω1​∣≤∣ω2​∣则称该产生式是非缔约的，如果一个文法所有的产生式都是非缔约的，则称这个文法是 非缔约的或者单调的。

3.语法分析树

对于上下文无关的语言，将其派生用有序根树表示成的图形叫做派生树，树根表示初始符，树的内部节点表示派生过程中产生的非终结符，叶结点表示终结符。

1. 自顶向下的语法分析：从初始符开始，用一系列替换派生出语句
2. 自底向上的语法分析：从语句开始推导需要的替换

4.巴克斯—诺尔范式

巴克斯—诺尔范式(BNF)是一种表示2型文法的方法。

1. 非终结符用<>括起来
2. 用“::=”代替 “ → \to →”
3. 产生式右侧多种可能用“|”隔开
   例：<A>::=<A>a|a|<A><B>

三、有限状态机

1.带输出的有限状态机

带输出的有限状态机是一个六元组 M = ( S , I , O , f , g , s 0 ) M=(S,I,O,f,g,s_0) M=(S,I,O,f,g,s0​)：

• S S S是有限状态的集合， s 0 s_0 s0​是初始状态,
• I I I是有限输入字母表,
• O O O是有限输出字母表,
• f f f是转移函数， f : S × I → S f: S \times I\to S f:S×I→S,
• g g g是输出函数， g : S × I → O g:S \times I \to O g:S×I→O.
  设 M M M是有限状态机，可以用状态表或状态图来表示 M M M

M M M是一个有限状态机， L ⊆ I L\subseteq I L⊆I，对于 L L L中的 x x x，如果 M M M的输出的最后一位是1，则称 M M M能识别 L L L.

有限状态集的类型：
米兰机：输出与状态之间的转移相对应
摩尔机：输出仅由状态决定

2.不带输出的有限状态机

不带输出的有限状态自动机是一个五元组 M = ( S , I , f , s 0 , F ) M=(S,I,f,s_0,F) M=(S,I,f,s0​,F)：

• S S S是有限状态集，
• I I I是有限输入字母表，
• 转移函数 f : S × I n → S f:S\times I^n \to S f:S×In→S，
• 初始状态 s 0 s_0 s0​，
• 终结状态集 F ⊆ S F\subseteq S F⊆S.

M M M是一个有限状态自动机，如果 x ∈ L x\in L x∈L将 s 0 s_0 s0​转变为一个终结状态，就称 M M M能识别 L L L.

有限状态自动机的等价：如果两个有限状态自动机能识别相同的语言，就说它们是等价的

四、图灵机

图灵机是一个四元组 T = ( S , I , f , s 0 ) T=(S,I,f,s_0) T=(S,I,f,s0​)

• S S S是有限状态集， s 0 s_0 s0​是初始状态
• I I I是包含空白符 B B B的输入字母表
• 部分函数 f = S × I → S × I × { L , R } f=S\times I\to S\times I \times\{L,R\} f=S×I→S×I×{L,R}

图灵机主要由控制器和带组成：带被分成无限个小方格，但任何时候带上只有有限个非空白符；在每一步，控制器读取当前方格中的符号 x x x，如果控制处于状态 s s s，且 f f f将 ( s , x ) (s,x) (s,x)映到 ( s ′ , x ′ , d ) (s',x',d) (s′,x′,d)，控制器进入状态 s ′ s' s′，擦掉当前方格中的 x x x并写上 x ′ x' x′，如果 d = R d=R d=R就右移一个方格， d = L d=L d=L就左移一个方格；如果部分函数 f f f在 ( s , x ) (s,x) (s,x)处没有定义，图灵机停机。
我们将每一记作 ( s , x , s ′ , x ′ , d ) (s,x,s',x',d) (s,x,s′,x′,d)
当输入 x x x时图灵机能够停机且停机时 y y y在带上，则称 T ( x ) = y T(x)=y T(x)=y，若输入 x x x时图灵机不停机，则 T ( x ) T(x) T(x)无定义

设 V ⊆ I V\subseteq I V⊆I，图灵机 ( S , I , f , s 0 ) (S,I,f,s_0) (S,I,f,s0​)能识别 V V V上的串 x    ⟺    T x \iff T x⟺T在初始状态时将 x x x写在带上 T T T能够停机；称 T T T能识别集 A A A如果 ( T (T (T能识别串 x    ⟺    x ∈ A ) x \iff x\in A) x⟺x∈A)