四种自动机与对应文法 有限自动机 下推自动机 图灵机 线性有界自动机ppt课件.ppt

《四种自动机与对应文法 有限自动机 下推自动机 图灵机 线性有界自动机ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、x

6、。例如

7、0100101

8、=7空串：不含

9、任何字符的串，即长度为零的串，记为。18语言及其表示前缀、后缀、子串19语言及其表示20语言及其表示串的逆：把一个串中的字符逆向顺序重新排列得到的另一个串设x为一个串，x的逆记为xR例：若x=0100101则xR=1010010易知1）

10、xR

11、=

12、x

13、2）空串的逆仍是空串：εR=ε21语言及其表示串的连接（concatenation）运算22语言及其表示串的幂运算串的连接运算又称为串的乘法运算。类似于从数的乘法运算推广到数的幂运算那样，也可以从串的乘法推广到串的幂运算。设x为一个串，则定义23语言及其表示24语言及其表示25语言及其表示语言（Language

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

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

16、和正规语言42有限自动机（finite