《四种自动机与对应文法-有限自动机-下推自动机-图灵机-线性有界自动机》由会员分享，可在线阅读，更多相关《四种自动机与对应文法-有限自动机-下推自动机-图灵机-线性有界自动机（115页珍藏版）》请在金锄头文库上搜索。
1、形式语言与自动机1参考文献2参考文献3参考文献4背景图灵机1936年首先由图灵（A.M.Turing）提出，他设计的自动机称为图灵机。5背景有限状态机又被称为有穷状态自动机、有限自动机1951年到1956年，克林(Kleene)在研究神经细胞中，建立了识别语言的系统有限状态机。6背景丘奇（Church）提出了一个假设：图灵机的计算能力代表着可实现的计算装置的基本范围。任何能在电子计算机上实现的计算都能用图灵机进行描述。7背景形式语言1956年，N.乔姆斯基（NoamChomsky）给出一种文法的数学模型。语言L定义为一个字母表中的字母组成的一些串的集合：L*。字母表上按照一定的规则定义一个文发
2、(grammar)，该文法所产生的所有句子组成的集合就是该文法产生的语言。8背景20世纪50年代，巴科斯范式(BackusNourForm或BackusNormalForm,BNF)实现了对高级语言ALGOL-60的成功描述。这一成功，使得形式语言在20世纪60年代得到了大力的发展，并使形式语言与编译原理紧密联系在一起。上述理论在编译原理、人工智能、可计算性和时序逻辑电路设计等领域有着广泛的应用。9语言理论自然语言自然语言：人与人之间交流的基本手段。 如：汉语、英语、俄语、法语、等人工语言人工语言：主要用于人与计算机之间的交流。 如：程序设计语言 语言自然语言人工语言10语言理论形式语言形式语
3、言：研究自然语言和人工语言都必须遵循的一般规律 研究字符串集合及其性质的学科Chomsky文法体系：4种类型的文法及其产生的语言 正规文法RG正规语言RL； 上下文无关文法CFG上下文无关语言CFL； 上下文有关文法CSG上下文有关语言CSL； 无限制文法URG递归可枚举语言r.e.。11自动机理论语言（形式语言）识别器 4种类型自动机与4类文法相对应 有限自动机FA RL RG 下推自动机PDA CFL CFG 线性界限自动机LBACSL CSG 图灵机TMr.e.URG12形式语言（FormalLanguage）13语言及其表示语言某个字母表上满足某些特定条件的字符串的集合自然语言人工语言
4、1.1字母表、串和语言字母表、串和语言字母表（字母表（Alphabet）：由字符组成的非空有限集，通常用表示。(sigma 西格马) 空 集 不能作为字母表 无限集 也不能作为字母表a,b,c,d0,114语言及其表示15语言及其表示16语言及其表示17语言及其表示串串（String）：）：由某字符表上的字符组成的有限序列。例如：0100101 是字母表=0,1上的一个串。串的长度串的长度：一个串中字符的个数。 设x为字母表上的一个串，x的长度记为|x|。例如 |0100101|=7空串：不含任何字符的串，即长度为零的串，记为 。18语言及其表示前缀、后缀、子串前缀、后缀、子串19语言及其表示
5、20语言及其表示串的逆：串的逆：把一个串中的字符逆向顺序重新排列得到的另一个串设x为一个串，x的逆记为xR例：若x=0100101则xR=1010010易知1）|xR|=|x|2）空串的逆仍是空串：R=21语言及其表示串的连接（串的连接（concatenation）运算运算22语言及其表示串的幂运算串的幂运算 串的连接运算又称为串的乘法运算。类似于从数的乘法运算推广到数的幂运算那样，也可以从串的乘法推广到串的幂运算。 设x为一个串，则定义 23语言及其表示24语言及其表示25语言及其表示语言（语言（Language）26语言及其表示语言几种基本运算语言几种基本运算27语言及其表示28语言及其表
6、示29语言及其表示句型、推导与句子句型、推导与句子30语言及其表示文法所产生的语言文法所产生的语言31语言及其表示举例举例32语言及其表示33语言及其表示34语言及其表示语言语言识别器识别器 语言识别器同文法一样，都是对（可能为无限集的）语言提供有限表示的一种方式。语言识别器也称为自动机。 如果说文法是从产生语言的角度来表示语言，那么自动机是从识别语言的角度来表示语言。 自动机的结构可以大致表示成下图的形式。辅助存储器a1a2an有限状态控制器图 自动机的大致结构35语言及其表示即自动机由部分组成：有限状态器、输入带和辅助存储器。有的自动机可以没有辅助存储器。 输入带可以有限长或无限长，有限状
7、态控制器对输入带可以只允许读，不允许写，也可以读和写。 根据不同的规定，自动机可以分为几种类型。36正规文法与有限自动机正规语言是Chomsky文法体系中最简单的一类语言。产生这种语言的文法是正规文法，识别这类语言的是有限自动机。此外，这类语言也可以用正规表达式表示。因此，正规语言也叫正规集。37正规表达式与正规集38正规表达式与正规集39正规表达式的性质40正规文法和正规语言正规文法是Chomsky文法体系中最简单的一种文法。说它简单，是指它的产生式的形式简单，因为产生式集是一个文法的核心。 定义和例子定义和例子41正规文法和正规语言42有限自动机（finiteautomaton,FA）43
8、有限自动机（finiteautomaton,FA）4445确定的有限自动机确定的有限自动机46确定的有限自动机确定的有限自动机47确定的有限自动机确定的有限自动机48确定的有限自动机确定的有限自动机49确定的有限自动机确定的有限自动机50确定的有限自动机确定的有限自动机51确定的有限自动机确定的有限自动机52不确定的有限自动机不确定的有限自动机53不确定的有限自动机不确定的有限自动机54不确定的有限自动机不确定的有限自动机55不确定的有限自动机不确定的有限自动机56不确定的有限自动机不确定的有限自动机57不确定的有限自动机不确定的有限自动机58带输出的有限自动机带输出的有限自动机59Moore
9、机60Moore机61Moore机62Moore机63Moore机64Mealy机机65Mealy机机66Mealy机机67Mealy机机68Moore机和机和Mealy机的等价性机的等价性69上下文无关文法与下推自动机70上下文无关文法(context-freegrammer）71上下文无关文法(context-freegrammer）72上下文无关文法(context-freegrammer）73上下文无关文法(context-freegrammer）74上下文无关文法(context-freegrammer）75推导树（derivationtree）76推导树（derivationtre
10、e）77推导树（derivationtree）78推导树与推导的关系推导树与推导的关系79最左推导与最右推导最左推导与最右推导80上下文无关文法的歧义性上下文无关文法的歧义性81上下文无关文法的歧义性上下文无关文法的歧义性82上下文无关文法的应用上下文无关文法的应用83上下文无关文法的应用上下文无关文法的应用84下推自动机（下推自动机（PushdownAutomaton）85下推自动机（下推自动机（PushdownAutomaton）86下推自动机（下推自动机（PushdownAutomaton）87下推自动机（下推自动机（PushdownAutomaton）88下推自动机（下推自动机（Pus
11、hdownAutomaton）89下推自动机（下推自动机（PushdownAutomaton）90下推自动机（下推自动机（PushdownAutomaton）91下推自动机（下推自动机（PushdownAutomaton）n例：构造PDAM，接受语言L(M)=anbnn1n思路：把输入的字符a入栈，当开始输入b时，从栈中弹出a，若a、b个数相同，则到达终态，且栈中空。n解：设PDAM（Q，T，q0，z0，F），Qq0，q1，q2q0初态；接受aq1状态；接受bq2状态；输入 回到q0 Ta,b, = z0, a, F = q0定义为：(q0，a，z0) = ( q1 ，a z0) (q1，a，
12、a) = ( q1 ，aa) (q1，b，a) = ( q2 ，) (q2，z0) = ( q0 ，) (q2，b，a) = ( q2 ，) 92下推自动机（下推自动机（PushdownAutomaton） 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，） 终态接受终态接受93确定的下推自动机确定的下推自动机94无限制文法无限制文法95无限制文法无限制文法96图灵机97图灵机98图灵机99图灵机100图灵机101图灵机102图灵机103图灵机104图灵机105图灵机106图灵机107上下文有关文法（上下文有关文法（context-sensitivegrammer，CSG）108上下文有关文法上下文有关文法109线性界限自动机（线性界限自动机（Linearboundedautomaton）110各种类型的语言之间的关系各种类型的语言之间的关系111各种类型的语言之间的关系各种类型的语言之间的关系112各种类型的语言之间的关系各种类型的语言之间的关系113ThankYou！114部分资料从网络收集整理而来，供大家参考，感谢您的关注！
