形式语言理论的研究对象 , 除了自然语言之外 , 还包括程序语言和其他人工语言。
如果一个语言存在对它的识别过程 , 则一定也存在对它的产生过程。反之亦然。
由此,刻画某类语言的有效手段, 是文法和自动机。
文法用来生成语言的句子, 自动机用来识别语言的句子 , 就描述一种语言 而言 , 两者是统一的。前者属于形式语法 理论 , 后者属于自动机理论(冯志伟 1979) 。
形式语法
组成
- 一个辅助词汇(auxiliary vocabulary)的有限集合——非终端语符(non-terminal symbol)集( 记为$V_N$)。有时也称变量。他们相当于各种句法范畴。
- 一个基本词汇(basic vocabulary)的有限集合——终端语符集(记为$V_T$)。若语法 生成的是自然语言 , 这些终端语符就相当于这种语言中 一个个具体的词。终端语符集就是这种语言的词典或词库。
- 一组由有限个重写规则(rewriting rule)组成的规则集(记为 $P$)。基本形式是$α→ β$。 即“ $α$ 改 写 为 $β$”或“ 由 $β$ 替 代 $α$”。 其 中 箭 头 表 示 指 令 。 一 条 规 则 就 是 一 个 机 械 性 的 操作程序 , 用来演算它联系着的两侧语符或语符序列之间的关系。
- 起始符。用 $S$ 表示。$S$ 即句子。$S∈V_N$ 。在语法生成句子的过程中,它至少有一次要出现在规则的左侧。
定义
一种形式语法$G= <V_N , V_T , P, S>$,其中,$S$表示起始符,$V_N$ 表示非终端语符集, $V_T$ 表示终端语符集 , $P$ 表示重写规则集 , 由有限个规则组成。
句子: 由语法 $G_0$ 从起始符 $S$ 可派生出来的终端语符列就构成了由 $G_0$ 生成的句子。
语言: 所有由语法 $G_0$ 从起始符 $S$ 可派生出来的终端语符列就构成了由 $G_0$ 生成的语言。
特点
- 高度的形式化和抽象化
- 形式语法是一套演绎系统
- 形式语法具有算法的特点
研究的必要性
- 形式语法是使语言学研究从描述性走向定性的惟一途径 , 即从个例研究走向范例研究(侯敏 1999)
- 形式语法是使自然语言成为现代化信息社会的媒体的技术支柱, 可按信息流处理
- 形式语法可帮助人们从纷乱复杂的表面现象中整理出有序的规律 , 有严格的推理步骤(侯敏 1999)
- 形式语法向自然语言处理提供先进的手段, 计算机要对自然语言进行句法分析, 首先要对语言研究的结果进行形式化描述 , 在对自然语言 形式化描述的基础上才能进一步分析(侯敏 1999)
语法的类型
- $0$ 型文法——短语结构文法 或 无约束文法
一种形式文法$G= <V_N , V_T , P, S>$,其中,$S$表示起始符,$S∈V_N$ ,$V_N$ 表示非终端语符集,$V_T$ 表示终端语符集, $P$表示重写规则(产生式)集,由有限个规则组成。$V= V_N ∪V_T$,如果 $P$ 中每个产生式可以描述为:$a→b$, $a∈V^+ (V 的正闭包)—V$ 中一个或多个符号序列, $b∈V^* (V 的自反闭包)—V$ 中零个或多个符号序列, 则称文法 $G$为 $0$ 型文法。
特点: 重写规则不受任何限制, 只要把规则左侧的语符改为右侧的语符就可以了。
- $1$ 型文法——上下文有关文法
上下文有关文法是一种无限制重写系统,它必须满足这样的规定:
一种形式文法$G= <V_N , V_T , P, S>$,其中,S表示起始符,$S∈V_N$,$V_N$表示非终端语符集,$V_T$ 表示终端语符集, $P$ 表示重写规则 (产生式)集, 由有限个规则组成。$V = V_N ∪V_T$ ,如果 $P$中每个产生式可以描述为:$x→y, x∈V^+ ,y∈V^*$ ,其中 $y$的长度大于等于 $x$ 的长度。或: $A→y/ x_z$ 或 $xAz→xyz$,即 $A$ 替换为 $y$是有条件的,即 $A$ 的前面必须 是 $x$,后面必须是 $z$。则称 $G$为上下文有关文法。
特点: 与 $0$ 型文法相比, 每条规则的左侧只能有一个非终端语符被改写,而且它的改写与上下文有关。
- $2$ 型文法——上下文无关文法
一种形式文法$G= <V_N , V_T , P, S>$,其中,S表示起始符,$S∈V_N$,$V_N$表示非终端语符集,$V_T$ 表示终端语符集, $P$ 表示重写规则 (产生式)集, 由有限个规则组成。$V = V_N ∪V_T$ ,如果 $P$ 每个产生式可以描述为: $A→x$, 其中 $A$ 是非终结符, $x$ 是空或多个终结符 和非终结符的序列。则 $G$是上下文无关文法。
注意:“上下文无关”这个名称指文法中重写规则的形式, 而不是指利用上下文来限制它所生成的语言。
特点: 跟 $1$ 型文法相比, 又多了一条限制, 即上一类语法重写规则的 $x$ 和 $z$ 必须是 “空”的 , 即非终端语符的改写不受它出现的语境制约。
- $3$ 型文法——正则文法
$3$ 型文法有两种格式:左线性文法和右线性文法。
左线性文法: $A→Bt$或$A→t$,其中$A$和$B$是非终结符,$t$是终结符。
右线性文法: $A→tB$或 $A→t$, 其中$A$和$B$ 是非终结符, $t$ 是终结符。
特点: $3$ 型文法与 $2$ 型文法相比, 又多了一个限制,即规则右侧最多只能有一个非终端语符。
四种类型语法的关系
从 $0$ 型文法到 $3$ 型文法,逐渐增加限制条件。类型级别每增加 $1$,限制逐渐增加,语法的生成能力反而随之减弱。$3$ 型文法限制最多 , 其生成能力最弱。
$1$ 型文法是 $0$ 型文法的特例;
$2$ 型文法是 $1$ 型文法的特例;
$3$ 型文法是 $2$ 型文法的特例。
自动机理论
一种可以用来对输入的符号序列进行检验和识别的装置。
- 图灵机(turing machine)
图灵机包括三个组成部分 : 有限控制器 , 输入纸带以及一个联系有限控制器跟输入纸带 的“ 读 写 头 ”$( r e a d i n g h e a d )$ 。
图灵机是一个七元组 $M= <Г, B, V, Σ, T, S_0 , F> $, 其中,$Г$是带符号的有限集合, $B$ 是 $Г$的一个符号, 即空白符, $V$ 是输入语符集, $V$ 中不包含 $B$,且 $V, Г,Σ$是自动机内部状态集,是有限集合, $S_0$ 是初始状态, $F$, $Σ$为终止状态集,$T$是一组转移规则或指令,有下面三种形式(翁富良, 王野翊 1998):
(1) $(a_i , S_j )→(a_k , S_1 )$
(2) $(a_i , S_j )→(R,S_1 )$
(3) $(a_i , S_j )→(L,S_1 )$
说明:
$a)$ 表示语符 $a_k$ 代替 $a_i$ , 但纸带不移动。控制器从状态 $S_j$ 到状态 $S_1$。
$b)$ 表示读入语符 $a_i$ , 纸带向右移动一格, 但读写头并不在纸带上写入任何语符。控制器从状态 $S_j$ 到状态 $S_1$ 。
$c)$ 表示读入语符 $a_i$ , 纸带向左移动一格, 但读写头并不在纸带上写入任何语符。控制器从状态 $S_j$ 到状态 $S_1$ 。
若一语言能为图灵机所识别 , 则它也能由 $ 0 $ 型文法生成 , 反之亦然。 如果我们把图灵机的内部状态集看作文法的非终端语符集 , 图灵机的输入语符集看作文法的终端语符集 , 而把图灵机的起始状态看作文法的起始符 , 则图灵机的三种转移规则转换成 $0$ 型文法的产生式规则 :
$(a_i , S_j )→(a_k , S_1 ) \quad\quad\quad S_j a_i →S_1 a_k$
$(a_i,S_j)→(R,S_1) \quad\quad\quad S_j a_i→a_i S_1$
$(a_i , S_j )→(L,S_1 ) \quad\quad\quad a_k S_j a_i→S_1 a_k a_i$
- 线性有界自动机(linear-bounded automaton)
线性有界自动机跟图灵机的构造基本一致 , 但与图灵 机相比 , 多了一个限制:它的读写头不能离开纸带输入语符列的两端。
线性有界自动机的形式系统与图灵机除 $V$ 外,其他一致。线性有界自动机中 $ V $ 中含 有两个特定符号 $&$ 和 $$$,分别是输入字符串左右两端的标志, 它们的作用是阻止读写头移出左右边界。
若一语言能为线性有界自动机所识别 , 则它也能由 $1$ 型文法生成 , 反之亦然。
如果我们把线性有界自动机的内部状态集看作文法的非终端 语符集 , 线性有界自动机的输入语符集看作文法的终端语符集 , 而把线性有界自动机的起始状态看作文法的起始符 , 则线性有界自动机的三种转移规则转换成 $1$ 型文法的产生式规则 :
$(a_i , S_j )→(a_k , S_1 ) \quad\quad\quad S_j a_i →S_1 a_k$
$(a_i,S_j)→(R,S_1) \quad\quad\quad S_j a_i→a_i S_1$
$(a_i , S_j )→(L,S_1 ) \quad\quad\quad a_k S_j a_i→S_1 a_k a_i$
- 有限自动机 (finite automaton)
有限自动机包括三个组成部分 : 有限控制器 , 输入纸带以及一个联系有限控制器跟输 入 纸 带 的“ 读 入 头 ”$( r e a d i n g h e a d )$ 。
有 限 自 动 机 是 一 个 五 元 组 $M = < V , Σ, T , S 0 , F >$ , $V$ 是 输 入 语 符 集 , $Σ$ 是 有 限 自 动机内部状态集,是有限集合,$S_0$ 是初始状态,$F, Σ$为终止状态集,$T$是一组转移规则或指令,
有这样的形式:$(a_i ,S_j )→S_k$ ,它表示:机器在状态 $S_j$ 如果读入语符 $a_i$ ,就转移到状态 $S_k$ ( J .E . 霍 普 克 罗 夫 特 , J .D . 厄 尔 曼 19 86 ) 。
若一语言能为有限自动机所识别 , 则它也能由 $3$ 型文法生成 , 反之亦然。
如果我们把有限自动机的内部状态集看作文法的非终端语符 集 , 有限自动机的输入语符集看作文法的终端语符集 , 而把有限自动机的起始状态看作文法的起始符,则有限自动机的转移规则转换成 $3$ 型文法的产生式规则 :
$(a_i , S_j )→S_k \quad\quad\quad S_j →a_i S_k$
- 下推自动机 (pushdown automaton)
下推自动机与有限自动机基本一致,但多了一个输出部分——栈 , 即输出部分按照后进先出的原则输出。
下推自动机是一个七元组$M=<V,Σ,T,S_0 ,F,Г,Z_0 >$,其中,$V$是输入语符集,$Σ$ 是自动机内部状态集 , 是有限集合 , $S_0$ 是初始状态 , $F, Σ$为终止状态集 , $Г$是输出语符集 , 是栈, $Z_0$ 是栈中起始符号, $T$ 是一组转移规则或指令, 有下面两种形式:
$(1) \quad(a_i , S_j , b_k )→(S_1 , b_m )$
$(2) \quad(a_i , S_j , b_k )→(S_1 , # )$
$(1)$ 表示下推自动机在状态 $S_j$ 和栈顶语符为 $b_k$ 时, 若输入语符 $a_i$ , 则输入纸带向左移 , 有限控制器转移到状态 $S_1$ , 在栈顶输出语符 $b_m$ 。
$(2)$ 表示下推自动机在状态 $S_j$ 和栈顶语符为 $b_k$ 时, 若输入语符$a_i$,则输入纸带向左移,有限控制器转移到状态 $S_1$ ,同时移去栈顶语符 $b_k$ 。(注:在栈顶输出$“ #”$相当于移去栈顶语符 $b_k$ )。
若一语言能为下推自动机所识别 , 则它也能由 $2$ 型文法生成 , 反之亦然。
用下推自动机来描述 $2$ 型文法识别一个句子的过程 :
自动机的读头自左至右扫描输入串 , 若栈顶一串符号与 $2$ 型文法某产生式右部相同 , 就把栈顶的符号替换成相应产生式 的左部非终结符 , 如不相同 , 就把输入符号移入栈内。这个过程一直进行直至输入串结束或拒绝接收(说明输入的句子不符合 $2$ 型文法) 。
乔姆斯基层级和自然语言
文法、自动机和语言的关系
| 类型 | 文法 | 自动机 | 语言 |
|---|---|---|---|
| $0$型 | 无约束短语结构文法 | 图灵机 | 递归可枚举语言 |
| $1$型 | 上下文有关文法 | 线性有界自动机 | 上下文有关语言 |
| $2$型 | 上下文无关文法 | 下推自动机 | 上下文无关语言 |
| $3$型 | 正则文法 | 有限自动机 | 正则语言 |
各种类型语言之间的相互关系 :
正则语言类真包含在上下文无关语言类中 ,
不含空字符串的上下文无关语言类真包含在上下文有关语言类中 ,
上下文有关语言类真包含在递归语言类中 ,
递归语言类真包含在递归可枚举语言类中。
用 2 型文法来生成自然语言比较合适