[音乐] 嗨，欢迎回来。
接下来呢，我们就来看看这个语言的分类。
那么语言的分类呢，从这个语法的分类开始，
那么我们说现代语言学家乔姆斯基他奠定了整个这个语言学研究的这个基础。
那么他在1956年提出了一个对于形式语法进行分类的这么一个分类体系。
那么他是基于这个短语结构语法的基础上来 讨论这个短语结构语法当中所包含的这个产生式关系，
也就是产生式的那个集合的特征来对这个语法，短语结构语法进行分类的。
那么首先呢，他是说如果对这个产生式没有任何的约束
你可以是自由格式的这么一个产生式，对产生式的左部和右部都没有任何约束的话 那么这个呢就称作一个叫做0型语法
或者也叫作无限制的语法，啊，或者 或者呢就称作一般性的叫做短语结构语法。
这是英语呢是PSG，就是一个短语结构语法。
那么短语结构语法呢，它可以产生这个递归可枚举语言 这个语言呢，就称作这一类就叫做递归可枚举。
那么这个词呢，我们以前没有接触过什么时递归；什么是可枚举，
那么将来呢我们在自动机的理论里头会涉及到。
那么说这个语言，这个语法所产生的语言 递归可枚举语言，它可以被这个图灵机所识别。
那么 图灵机呢我们在我们这一章形式语言自动机的这一章的后边 会具体的讲到图灵机是什么，以及它的功能是什么样的；
所以呢我们首先它是一个有这个0型语法，没有任何限制的0型语法。
那么如果把，对这个所有的产生式做一个进一步的限制
那么我们说如果说所有的产生式都像这个样子 是αAβ然后能够替换成αγβ
那当然这个αβ是一样的，也就是说实际上就是把这个
一个字符串当中，把这个A，非终结符A替换成一个γ，一个这么一个字符串
那么也就是说A是非终结符，然后α，β，γ都是任意的串 但是呢它有一个限制，就是γ不能为空串；
那既然不能为空串呢，那这个意思就是说这个产生式它所
利用这个产生式推出来的，导出的这个字符串它不会变的越来越短， 那么也就是说它只会比
比原来长，或者说保持原来的长度 它不会越来越短，这样的。
那么我们就把所有的产生式都满足这样的一个 形式的这种语法呢就称之为1型语法
那或者说叫做上下文相关语法，叫做CSG，上下文相关。
那么这里头的所谓的上下文，那么也就是说我在替换这个把A这个
非终结符替换成γ这个串的时候，我不能够随便替换
我们必须呢要在A的左边是α，右边是β的情况下，才能够把它替换成γ
所以呢，如果说另外一个上下文，就是A呢出现在左边是α撇，右边是β撇
那么它可能会可以替换成另外一个字符串，是吧？上下文不同
那么它可能能够替换的串可能也不一样，所以呢这叫做上下文相关，是这个意思。
那么它所产生的语言呢就叫做上下文相关语言。
那么这个语言呢可以被另外一个自动机所识别，叫做线性有界自动机。
那么在我们这门课上呢，我们并不打算来详细的介绍线性有界自动机
这个在其它的课程里面会有提到过 那么我们这呢，只介绍它一个名字就可以了。
那么如果再进一步的限制 如果所有的产生式作部都是一个单个的非终结符
比如说像α导出γ，这样的形式，那么γ呢可以是任意的串 那么我们就把这种语法，就称之为2型语法；
或者叫做上下文无关的语法，CFG，Free Grammer。
就是，这里的所谓的上文无关，也就是说这个不管这个
非终结符A出现在任何的这个字符串的任何的位置，或者说它的
，前面后面的这个字符串的情况，是什么样的情况都不管，
那么我随时都可以把A替换成γ，那么A呢也 只能够替换成γ，对吧？是这样子的。
所以呢它叫做上下文无关 那么上下文，2型语法或者叫上下文无关语法呢产生上下文无关语言
那么这个语言呢，能够被下推自动机所识别。
那么所谓的下推自动机呢，就涉及到有堆栈这些结构的
当然我们在我们的离散数学课上呢，也没有打算去介绍这个机器；
你们呢也是知道一下这个名字就可以了。
那么我们要特别的指出的是，这个上下文无关的语法呢是大多是程序设计语言
它的语法提供的一个理论的基础，也就是说大多数的这个程序设计语言
它的语法呢都是上下文无关的语法； 那么而且呢，所以呢我们在编译原理当中对这个源代码进行编译的时候
那么都会涉及到这个CFG它的所谓的理论，那么也会用到下推自动机。
如果再进一步的限制，也就是说所有的产生式左部
是只有一个非终结符，而且呢能右部也最多只能有一个非终结符
而且呢，还只能够出现在右部的最右边，最右边，也就是
说最右边呢只能是最，只能是单个非终结符，然后呢 其它的字符串都必须是终结符。
那这样的 一个满足这么严格限制的语法呢，就称之为3型语法
或者叫做正则语法，而这个正则语法呢就跟我们，实际上跟我们这个正则表达式确实是有- 联系的；
但是，具体什么样的联系，它，它们之间是一个什么样的关系，我们留到后边再来介绍。
那么正则语法就产生正则语言， 它能够被有限状态自动机来识别
那么这个有限状态自动机，我们下面，下周就会 马上就可以提到，就可以讲到这个什么是有限状态自动机
以及呢它是如何运作的。
那么正则语法所产生的正则语言，它也可以用正则表达式来进行表示，
那么具体的严格的证明，我们还会再，再提起。
那么正则语言或者正则语法，它通常用来定义这个我们在
进行检索，比如说在文件系统当中检索这个 文件的时候，我们会用到比如说*.doc呀这样的
它作为一个检索的模式的定义，或者呢是在程序设计语言当中，它不用来描述，它不是用来- 描述语法
那我们知道语法呢，它是上下文无关的语法 但是，但是呢在程序设计语言当中，还有一类的那个特殊的一些
标识符呀，或者是说整数呀这些，它是作为一个词，它的作为词法结构呢
它是一个正则语法来描述它的这个词的结构的
那么这样呢，我们有了这个形式语法以后，我们就可以对这个语言 来进行分类。
我们说对应于这个形式语法，如果说某一个语言 可以用某一个3型语法来产生的话，因为我们说3型语法它的限制
是最多的，如果可以用3型语法产生，那么就把它称之为3型语言
那么进一步的，如果说某一个语言不能够用任何的3型语法来产生的话
那么我们就回过头去再找 这个限制少一些的上下文无关语法，就是2型语法。
而如果我们发现，它这个语言可以用某个2型的语法来产生，那好
正好到了这个2级，2型语法这了，我们就可以把这个语言称之为 2型的语言。
那么，以此类推，那么就会有1型的语言和0型的语言而；
那么这样呢我们把它记一下，用这个符号来记，L3，3型
语言，L2，2型语言，L1，1型语言，L0，0型语言 那么这样呢我们可以知道，0型语言呢是一个最全的一个大集
那么而3型语言它是范围最小的，因为它也是限制最严格的这么一些
这么一类的语言，所以呢这个呢涉及到形式语言的分类 它是依据语法来进行分类的。
陈斌副教授
