四种自动机及对应文法 有限自动机 下推自动机 图灵机 线性有界自动机

1、形式语言与自动机1参考文献2参考文献3参考文献4背景5 图灵机 1936年首先由图灵（A. M. Turing）提出，他设计的自动机称为图灵机。背景6 有限状态机 又被称为有穷状态自动机、有限自动机 1951年到1956年，克林(Kleene)在研究神经细胞中，建立了识别语言的系统有限状态机。背景7 丘奇（Church）提出了一个假设：图灵机的计算能力代表着可实现的计算装置的基本范围。 任何能在电子计算机上实现的计算都能用图灵机进行描述。背景8 形式语言 1956年，N. 乔姆斯基（Noam Chomsky）给出一种文法的数学模型。语言L定义为一个字母表中的字母组成的一些串的集合：L *。 字

2、母表上按照一定的规则定义一个文发(grammar)，该文法所产生的所有句子组成的集合就是该文法产生的语言。背景9 20世纪50年代，巴科斯范式(Backus Nour Form 或 Backus Normal Form, BNF)实现了对高级语言ALGOL-60的成功描述。这一成功，使得形式语言在20世纪60年代得到了大力的发展，并使形式语言与编译原理紧密联系在一起。 上述理论在编译原理、人工智能、可计算性和时序逻辑电路设计等领域有着广泛的应用。语言理论10自然语言自然语言：人与人之间交流的基本手段。 如：汉语、英语、俄语、法语、等人工语言人工语言：主要用于人与计算机之间的交流。 如：程序设计

3、语言 语言自然语言人工语言语言理论11形式语言形式语言：研究自然语言和人工语言都必须遵循的一般规律 研究字符串集合及其性质的学科Chomsky文法体系：4种类型的文法及其产生的语言 正规文法RG正规语言RL； 上下文无关文法CFG上下文无关语言CFL； 上下文有关文法CSG上下文有关语言CSL； 无限制文法URG递归可枚举语言r.e.。自动机理论12语言（形式语言）识别器 4种类型自动机与4类文法相对应 有限自动机FA RL RG 下推自动机PDA CFL CFG 线性界限自动机LBACSL CSG 图灵机TMr.e.URG形式语言（Formal Language）13语言及其表示14 语言某

4、个字母表上满足某些特定条件的字符串的集合自然语言人工语言1.11.1字母表、串和语言字母表、串和语言字母表（字母表（Alphabet）：由字符组成的非空有限集，通常用表示。(sigma 西格马) 空 集 不能作为字母表 无限集 也不能作为字母表 a,b,c,d 0,1语言及其表示15语言及其表示16语言及其表示17语言及其表示18 串（串（String）：）：由某字符表上的字符组成的有限序列。例如：0100101 是字母表=0,1上的一个串。 串的长度串的长度：一个串中字符的个数。 设x为字母表上的一个串，x的长度记为|x|。例如 |0100101|=7空串：不含任何字符的串，即长度为零的串，

5、记为 。语言及其表示19前缀、后缀、子串语言及其表示20语言及其表示21串的逆：把一个串中的字符逆向顺序重新排列得到的另一个串 设x为一个串，x的逆记为xR 例： 若x=0100101 则xR=1010010 易知 1）|xR|=|x| 2）空串的逆仍是空串：R=语言及其表示22串的连接（串的连接（concatenation）运算）运算语言及其表示23串的幂运算串的幂运算 串的连接运算又称为串的乘法运算。类似于从数的乘法运算推广到数的幂运算那样，也可以从串的乘法推广到串的幂运算。 设x为一个串，则定义 语言及其表示24语言及其表示25语言及其表示26语言（Language）语言及其表示27语言

6、几种基本运算语言几种基本运算 语言及其表示28语言及其表示29语言及其表示30 句型、推导与句子句型、推导与句子语言及其表示31文法所产生的语言文法所产生的语言语言及其表示32举例举例语言及其表示33语言及其表示34语言及其表示35 语言识别器语言识别器 语言识别器同文法一样，都是对（可能为无限集的）语言提供有限表示的一种方式。语言识别器也称为自动机。 如果说文法是从产生语言的角度来表示语言，那么自动机是从识别语言的角度来表示语言。 自动机的结构可以大致表示成下图的形式。辅助存储器a1a2an有限状态控制器图 自动机的大致结构语言及其表示36即自动机由部分组成：有限状态器、输入带和辅助存储器。

7、有的自动机可以没有辅助存储器。 输入带可以有限长或无限长，有限状态控制器对输入带可以只允许读，不允许写，也可以读和写。 根据不同的规定，自动机可以分为几种类型。正规文法与有限自动机37 正规语言是Chomsky文法体系中最简单的一类语言。产生这种语言的文法是正规文法，识别这类语言的是有限自动机。此外，这类语言也可以用正规表达式表示。因此，正规语言也叫正规集。正规表达式与正规集38正规表达式与正规集39正规表达式的性质40正规文法和正规语言41 正规文法是Chomsky文法体系中最简单的一种文法。说它简单，是指它的产生式的形式简单，因为产生式集是一个文法的核心。 定义和例子 正规文法和正规语言4

8、2有限自动机（finite automaton,FA）43有限自动机（finite automaton,FA）4445确定的有限自动机确定的有限自动机46确定的有限自动机确定的有限自动机47确定的有限自动机确定的有限自动机48确定的有限自动机确定的有限自动机49确定的有限自动机确定的有限自动机50确定的有限自动机确定的有限自动机51确定的有限自动机确定的有限自动机52不确定的有限自动机不确定的有限自动机53不确定的有限自动机不确定的有限自动机54不确定的有限自动机不确定的有限自动机55不确定的有限自动机不确定的有限自动机56不确定的有限自动机不确定的有限自动机57不确定的有限自动机不确定的有限

9、自动机58带输出的有限自动机带输出的有限自动机59Moore机60Moore机61Moore机62Moore机63Moore机64Mealy机机65Mealy机机66Mealy机机67Mealy机机68Moore机和机和Mealy机的等价性机的等价性69上下文无关文法与下推自动机70上下文无关文法(context-free grammer）71上下文无关文法(context-free grammer）72上下文无关文法(context-free grammer）73上下文无关文法(context-free grammer）74上下文无关文法(context-free grammer）75推导树

10、（derivation tree）76推导树（derivation tree）77推导树（derivation tree）78推导树与推导的关系推导树与推导的关系79最左推导与最右推导最左推导与最右推导80上下文无关文法的歧义性上下文无关文法的歧义性81上下文无关文法的歧义性上下文无关文法的歧义性82上下文无关文法的应用上下文无关文法的应用83上下文无关文法的应用上下文无关文法的应用84下推自动机（下推自动机（Pushdown Automaton）85下推自动机（下推自动机（Pushdown Automaton）86下推自动机（下推自动机（Pushdown Automaton）87下推自动机（

11、下推自动机（Pushdown Automaton）88下推自动机（下推自动机（Pushdown Automaton）89下推自动机（下推自动机（Pushdown Automaton）90下推自动机（下推自动机（Pushdown Automaton）91下推自动机（下推自动机（Pushdown Automaton）92n例：构造PDA M，接受语言L(M)= anbnn1n思路：把输入的字符a入栈，当开始输入b时，从栈中弹出a， 若a、b个数相同，则到达终态，且栈中空。n解：设PDA M（Q，T，q0，z0，F）， Qq0 ，q1 ，q2 q0 初态；接受a q1状态；接受b q2状态；输入 回

12、到q0 Ta,b, = z0, a, F = q0定义为：(q0，a，z0) = ( q1 ，a z0) (q1，a，a) = ( q1 ，aa) (q1，b，a) = ( q2 ，) (q2，z0) = ( q0 ，) (q2，b，a) = ( q2 ，) 下推自动机（下推自动机（Pushdown Automaton）93 q a, Z/ p表示（p，）（q，a，Z）n上例的图形表示： a, z0/az0 b, a/ a, a/aa b, a/, z0/q0q2q1用格局表示aabb的识别过程:(q0 ，aabb，z0)（q1，abb，az0） （q1，bb，aaz0） （q2，b，az0） （q2，z0） （q0，） 终态接受终态接受确定的下推自动机确定的下推自动机94无限制文法无限制文法95无限制文法无限制文法96图灵机97图灵机98图灵机99图灵机100图灵机101图灵机102图灵机103图灵机104图灵机105图灵机106图灵机107上下文有关文法