本课程为电子科技大学陈文宇老师主讲的形式语言与自动机课程教学视频,全套课程共27集,形式语言与自动机是高等院校计算机专业的学习课程,涵盖内容丰富,而且有很强的应用价值。形式语言指按一定规律构成的句子或符号串的有限或无限的集合,下面我们就来了解一下。
形式语言的特点
1,高度的抽象化(采用形式化的手段-专用符号,数学公式-来描述语言的结构关系,这种结构关系是抽象的)
2,是一套演绎系统(形式语言本身的目的就是要用有限的规则来推导语言中无限的句子,提出形式语言的哲学基础也是想用演绎的方法来研究自然语言)3,具有算法的特点.(比如说句法分析中采用不同的算法来构造句子的句法推导树)
乔姆斯基把文法分成4种类型,即0型,1型,2型,和3型。
0型文法也称短语文法,0型文法的能力相当于图灵机(Turing),或者说任何0型语言都是递归可枚举的。
1型文法也称上下文有关法,其能力相当于线性界限自动机。
2型文法也称上下文无关法,其能力相当于非确定的下推自动机。
3型文法也称右线性文法,由于这种文法等价于正规式,所以也称正规文法。从文法描述语言的能力来说,0型文法最强,3型文法最弱。