形式语言与自动机

形式语言

1.形式语法定义

无论哪种语言都是句子和符号串的集合，描述一种语言的三种方法：
1. 穷举法：把语言中的所有句子都枚举出来。
2. 文法描述：语言中的每个句子用严格定义的规则来构造，利用规则生成语言中合法的句子。（用来精确地描述语言和其结构）
3. 自动机法：通过对输入的句子进行合法性检验，区别哪些是语言中的句子，哪些不是。（用来机械地刻画对输入字符串的识别过程）

定义（形式语法）：一个四元组G=（N，∑，P，S），其中N是非终结符的有限集合；∑是终结符号的有限集合，N∩∑=∅；V=N∪∑称为总词汇表；P是一组重写规则的有限集合：P={α->β}，其中α，β是由V中元素构成的串，但是α中至少应含有一组非终结符号；S∈N称为句子符或初始符。

附录【字符串的闭包运算】字符表∑上的符号串集合V的闭包定义为：V*=V0∪V1∪V2∪….，V+=V1∪V2∪….(或 V*-{ε})。
e.g.: V={a,b},则 V*={ ε,a,b,aa,ab,bb,ba,aaa,…} V+={a,b,aa,ab,bb,ba,aaa,…}

定义（推导）：设G=（N，∑，P，S）是一个文法，在(N∪∑)*上定义关系 =G=> 为：
如果αβγ是 (N∪∑)*中的字符串，且β->δ是P中的一个产生式，那么αβγ =G=> αδγ。

按非平凡方式派生 =G+=>：表示=G=>的传递闭包，即(N∪∑)*上的符号串ξi到ξi+1（i>=0）至少经过一步推导或派生。
派生=G*=>：表示=G=>的自反或传递闭包，即由(N∪∑)*上的符号串ξi到ξi+1经过n（n>=0）步推导或派生。
这里写图片描述
【其中最右推导为规范推导】

定义（句子）文法G=（N，∑，P，S）的句子形式通过如下递归方式定义：1）S是一个句子形式；2）如果γβα是一个句子形式，且β->δ是P中的产生式，那么γδα也是一个句子形式。
对于文法G，不含非终结符的句子形式成为G生成的句子。由文法G生成的语言（或称G识别的语言）是指G生成的所有句子集合，记作 L(G)={x|x∈∑，S=G*=>x}。

2.形式语法的类型

正则文法（3型文法）

定义（正则文法）：如果文法G的规则集P中所有规则均满足如下形式：A->Bx，或A->x，其中A,B∈N，x∈∑，则称该文法G为正则文法。

A->Bx为左线性正则文法
A->xB为右线性正则文法

这里写图片描述

上下文无关文法（2型文法）

定义（上下文无关文法）：如果文法G的规则集P中所有规则均满足如下形式：A->α，其中A∈N，α∈(N∪∑)*，则称文法G为上下文无关文法（CFG，context-free grammar）。
这里写图片描述

上下文有关文法（1型文法）

定义（上下文有关文法）：如果文法G的规则集P中所有规则满足如下形式：αAβ->αγβ，其中A∈N，α，β，γ∈(N∪∑)*，且γ至少包含一个字符，则称文法G为上下文有关文法（CSG，context-sensitive grammar）。
从定义可以看出，字符串αAβ中的A被改写成γ时需要有上文语境α和下文语境β。当α和β为空字符 ε时，1型文法变成了2型文法，即2型文法是1型文法的特例。
这里写图片描述
通过这个例子看出，规则左部不一定仅为一个非终结符，可以有上下文限制，但规则右端的长度不小于规则左部的长度。
因此该文法另一种定义：如果文法G为上下文有关文法，当且仅当x->y，x∈(N∪∑)+，y∈(N∪∑)*，并且|y|>=|x|。

无约束文法（0型文法）

定义（无约束文法）：如果文法G的规则集P中所有规则满足如下形式：α->β，其中α∈(N∪∑)+，β∈(N∪∑)*，则称G为无约束文法或无限制重写系统。
这里写图片描述

3.CFG识别句子的派生树表示

一个上下文无关文法G=（N，∑，P，S）产生句子的过程可以由派生树（语法树/分析树/推导树）表示。
派生树构造步骤：
这里写图片描述
定义（二义性文法）：如果文法G对于同一个句子存在两棵或者两棵以上不同的分析树，那么该句子是二义性的，文法G为二义性文法。

自动机理论

有限自动机（FA，finite automatic）

1.确定性有限自动机（DFA，definite automata）

定义（确定性有限自动机）DFA M是一个五元组：M=（∑，Q，δ，q0，F）。其中∑是输入符号的有穷集合；Q是状态的有限集合；q0∈Q是初始状态；F⊆Q是终止状态集合；δ是Q与∑的直积Q×∑到Q（下一个状态）的映射，它支配着有限状态控制的行为，有时也称为状态转移函数。
这里写图片描述
原理：处在状态q∈Q中的有限控制器从左到右依次从输入带上读入字符。开始时有限控制器处在状态q0，输入头指向∑*中一个链的最左符号。映射δ(q,a)=q’ （q,q’∈Q，a∈∑）表示在状态q时，若输入符号为a，则自动机M进入状态q’并且将输入头向右移动一个字符。
定义（DFA接受的语言）如果一个句子x对于有限自动机M有δ(q0,x)=p，p∈F，则称句子x被M接受。被M接受的句子的全集称为由M定义的语言，或称M所接受的语言，记作T(M)={x | δ(q0,x)∈F}。

用状态图描述映射δ，δ(q,a)=q’的状态转换图如下：
这里写图片描述

状态转换图的构造方法：每个状态作为一个节点，用圆圈表示。如果处在状态q并接受输入符号a∈∑时的DFA转移到q’状态，那么画一条有向弧从状态q到达状态q’，标记为a。终止状态用双圈表示，开始状态用带“开始”说明的箭头标出。
这里写图片描述
该DFA识别的语言为“所有0、1构成的至少包含一个0的字符串”。

2.不确定性有限自动机（NFA，non-definite automata）

定义（不确定的有限自动机）NFA M是一个五元组：M=（∑，Q，δ，q0，F）。其中∑是输入符号的有穷集合；Q是状态的有限集合；q0∈Q是初始状态；F是终止状态集合，F⊆Q；δ是Q与∑的直积Q×∑到Q的幂集2^Q的映射。

NFA与DFA的重要区别是：在NFA中δ(q,a)是一个状态集合，而在DFA中δ(q,a)是一个状态。根据定义，对于NFA M有映射：δ(q,a)={q1,q2,…,qk},k>=1。
即NFA M在状态q时，接受输入符号a时，M可以选择状态集q1,q2,…,qk中任何一个状态作为下一个状态，并将输入头向右边移动一个字符的位置。

定义（NFA接受的语言）如果存在一个状态p，有p∈δ(q0,x)且p∈F，则称句子x被NFA M所接受。被NFA M接受的所有句子的集合称为NFA M定义的语言，记作T(M)={x | p∈δ(q0,x) 且 p∈F}。

定理：设L是被NFA所接受的语言，则存在一个DFA，它能够接受L。

3.正则文法与自动机的关系

重要结论：对于任意一个正则文法所产生的语言，总可以构造一个确定的有限自动机识别它。（即对任意一个正则文法，总可以构造一个确定的有限自动机）
两个定理
G->FA
这里写图片描述
FA->G

e.g.:

下推自动机（PDA，push-down automata）

下推自动机（PDA）可以看成是一个带有附加下推存储器的有限自动机，下推存储器是一个堆栈（stack）。原理示意图如下：
这里写图片描述
定义（PDA）不确定的下推自动机可以表达成一个七元组：M=(∑，Q，τ，δ，q0，Z0，F)。其中∑是输入符号的有穷集合；Q是状态的有限集合；τ为下推存储器符号的有穷集合；q0∈Q是初始状态；Z0∈τ为最初出现在下推存储器顶端的开始符号；F⊆Q是终止状态集合；δ是从Q×(∑∪{ ε})×τ到Q×τ*的子集的映射。

这里写图片描述

图灵机（Turing machine）

图灵机VS有限自动机，图灵机可以通过其读写头改变输入带上的字符。

定义（图灵机）一个图灵机T可以表达成一个六元组：T=(∑，Q，τ，δ，q0，F)。其中∑是输入/输出带上字符的有穷集合，不包含空白符号B；Q是状态的有限集合；τ是输入符号的有穷集合，包含空的符号B，∑⊆τ，τ=∑∪{B}；q0∈Q是初始状态；F⊆Q是终止状态集合；δ是从Q×τ到Q×(τ-{B})×{R，L，S}子集的一个映射。其中R,L,S分别表示右移一格，左移一格和停止不动。
这里写图片描述

线性界限自动机（linear-bound automata）

线性界线自动机是一个确定的单带图灵机，其读/写头不能超越原输入带上字符串的初始和终止位置，即线性界线自动机的存储空间被输入符号串的长度所限制。

定义（线性界线自动机）一个线性界线自动机M可以表达成一个六元组：M=(∑，Q，τ，δ，q0，F)。其中τ是输入/输出带上符号的有穷集合；Q是状态的有限集合；∑是输入/输出带上字符的又穷集合，∑⊆τ；q0∈Q是初始状态；F是终止状态集合，F⊆Q；δ是从Q×τ到Q×τ×{R,L}子集的映射。
∑包括两个特殊符号#和$，分别表示输入链的左端和右端结束标志。
这里写图片描述