[音乐] 海，欢迎回来。
接下来我们来看一看这个 几个语法的这个实例，以及语法所产生的语言。
那么我们说呢，就是一个短语结构语法，它是由 4个元素构成的，就是字符集，终结符的集合，
以及这个起始的符号，一个非终结符，以及这个产生式关系。
它是，这是一个这么一个四元组。
那么我们也说了，就是从这个 整个这个四元组开始，我们可以从V0开始呢导出各种各样的
只包含有终结符的这些字符串。
那么这样呢，我们说 所有的利用语法G所产生的所有正确构造的这些句子，
当然这个句子呢只包含有这个终结符，它不包含任何的非终结符。
那么把所有的这样的一个语法正确的句子都收集在一起，所有的啊，
那么所形成的集合呢就称作为G所对应的语言。
我们就把它记作为L(G)，L(G)呢就是G所代表的这个语言，或者说描述的 这个语言。
那当然我们知道语言就是字符串的集合，所以呢它也是一个字符串的集合。
那么我们必须要指出来，只要 不同的这个语法它可能会产生不同的语言，
当然呢，不同的语法也可能产生相同的语言。
你可能 不同的表达方式，但是最终呢它表达出来的这个字符串的 集合是相等的两个集合。
那这样呢，它也可能会产生相同的 语言。
那么整个的这个导出的这个过程对于一些
语法来说，我们可以用一些树的形式来表示它，就所谓的，叫做导出树。
那么导出树呢是用一个，是一个多元的有向树， 它可以用来表示这个整个的语言它被生成的一个过程。
那么它以这个起始符号v0作为树根，因为所有的这个导出都是从
树根从v0开始的，所以我们从v0作为树根， 然后呢每一个子树，树根呢会有每一个
子树，那么子树的树根就是这个树根的所有的子结点， 它就是某一个产生式的这个左步。
然后呢子结点呢分别是 产生式的这个右部所包含的这些符号，那么一个个按照顺序
排成它的所有的子结点。
那么这个呢，因为我们知道 树结构它的，按照图论来说，树结构，根树的结构，它的树根只有一个。
那么既然树根是产生式的左步，那么所以呢我们导出树的这种方式
用来表示这个语法的导出过程的时候，它就只合适那些 所有的产生式的左步都只有一个非终结符的情况。
都只有一个非终结符，这样的一个情况。
我们来看看一个例子。
这个例子呢是V，字符集合是v0,w,a b,c，然后其中呢a,b,c是终结符，而v0和w是
非终结符，那么它的产生式呢包含这三个产生式。
一个是v0能够导出aw，然后第二个呢是w变成bbw，
第三个呢，是w替换成c，那这样呢，我们说这个L(G)，就是G所产生的 语言它就是S*的一个子集了。
那好，我们 来看看一个按照导出树如何来描述这样的一个过程。
我们从这个树根开始，就是v0，
我们引用，因为以v0作为左部的产生式只有一个，所以呢我们引用了aw，
那么它的这个子结点，左子结点是a，然后右边第二个子结点是w，
而w呢是一个非终结符，非终结符呢以它为
开头的有两个产生式，一个是呢bbw，另外一个呢是替换成c。
所以我们呢选用了bbw，那这样的树呢有三个子结点， 一个b，一个b，一个w。
然后接下来呢我们还可以在这两个当中去选。
但是呢我们只要说如果一直只是选第二个产生式，就是w
替换成bbw的话，那么我们永远都不能够得到一个句子。
最终如果我们希望得到一个只包含有 终结符的这么一个句子的话，我们就只能够引用第三个产生式，w替换成c。
那么最后呢w替换成c这样的一个形式。
那这样呢如果我们 经过这个第一次、 第二次、 第三次，四次的这个导出，直接导出的话，
我们就得到了一个由终结符构成的一个句子，就是a，然后呢bb，
再bb，最后是c，这样的一个句子。
那么我们来分析它这个句子的这个模式，我们会发现呢它是以a开始，
以c结尾，然后中间呢若干个bb的重复。
那这样呢，我们实际上可以用一个正则表达式来表示这样的一个字符串的集合。
那么也就是a，然后bb*,然后c，那这个呢也同样是a开始， 然后c结束。
然后中间有若干个bb重复的这么一个字符串的所有的集合。
所以呢我们发现呢，就是用这个 短语结构语法所描述，它所产生的这个语言L(G),
实际上呢它有，它也同样可以用正则表达式来进行描述。
那从这个方面来说，这个正则表达式和短语结构语法它们 是等价的，它们都可以描述同一个语言。
我们看看第二个语法的例子。
我们V,S呢同上，也都是，S也是a,b,c， 但是呢我们的产生式呢换成另外三个。
这三个呢就跟原来的刚才的那个有点不一样。
那么第一个呢是v，v0变成av0b，
第二个呢是v0b变成bw，而那这样呢 我们看到首次出现了说产生式的左部有两个符号，
其中一个呢是非终结符，一个是终结符，它出现了两个符号，那确实有点奇怪。
然后第三个呢就更是了，它第三个呢是左部是 三个符号，abw，然后把abw呢替换成c。
那么这三个产生式综合起来，它能够产生什么样的一个字符串的集合呢？ 我们来分析一下。
那么我们看第一个产生式， 它如果反复地调用，因为第一个产生式v0变成av0b，
那我们发现了它所导出的这个av0b当中还有
v0，那我们就可以反复地不停地用这个第一个产生式若干次。
如果你用n次之后呢，我们就发现呢它产生的串呢是
a的n次幂，b的n次幂，就是前面呢有n个a，后面呢有n个b，然后中间呢还是v0.
这样的一个串，那么这个n呢你可以是随意的。
你是重复一千次，那么就有一千个a，一千个b，中间是v0.
如果是一万次，那就一万个a，一万个b，中间是v0，那这样的一个串。
所以呢，你如果反复地用第一个产生式，它就会产生这种类型的串。
那么到了第二阶段，我们应用第二个产生式 的话，我们就会发现呢它会把v0b换成bw，
那这样呢，它就会变成abw在中间，这时候呢a和b的这个数量呢还是一样的。
然后左边的是m个a，右边的是m个b。
那这样呢，中间有一个abw，产生一个这样的一个形式的 这个字符串。
那么但是呢，这么替换以后， 它就不能再重复地用第二个产生式了。
但是呢它中间呢还包含了一个非终结符，就是w。
那么我们最终要想得到这个句子， 那我们只能引用最后这个产生式，就是abw替换成c，
那么这样，替换用了第三个产生式来消除
这个非终结符的话，那么最终呢它这个结果呢，就是L(G)呢就是像 am，bm，中间加一个c这样的状况。
那么这个中间呢 整个的字符串可以这么描述，就是中间有c，然后c的左边
有若干个a，然后c的右边呢有若干个b，然后a的b，数量和b的数量是相同的。
那么它描述了这么一个字符串的集合，所以呢也就是描述了这么一个语言。
那么我们必须指出来，像L(G) 就是这样的一个语言，它是不能够用正则表达式来表示的。
但是为什么呢？我们这里头也没有办法去证明它，在我们这个课上。
但是回头我们会用另外的一个机制回过头来 证明它是不是一个正则表达式所能够表达的语言。
那么不管怎么样呢，我们可以发现，可见说
我们用了两个短语结构语法，一个短语结构所产生的语言可以用正则表达式来表示，
另外一个语法产生的语言却不能够用正则表达式来表示，那可见呢
语言和语言之间，字符串集合和字符串集合之间 有某种类型上的一些差异。
那么具体差异 是什么呢？我们下一节我们就能知道了。
陈斌副教授
