[音乐]
Hi，欢迎回来，接下来我们来看看关于正则的一切。
我们在最最早的时候学到了这个正则表达式，然后说正则表达式它所对应的这个集合，
正则上称作一个正则集合，后来我们在进行语法分类的时候，我们分出一类的这个语法， 称作为正则语法。
那么正则语法所产生的语言，叫做正则语言。
那么这 两个体系它们都是有正则这么一个意味的， 都有这么一个术语。
那么到底由正则表达式所 产生的正则集合和正则语法所产生的正则语言
那么这两个体系之间它们有什么样的一个关系呢？我们来看看这个定理，它就说明了这么一- 个关系。
这个定理说S是一个有限集合，这个L呢是
S*的一个子集，那么也就是说S是一个终结符，它只包含一些 终结符作为这个字符。
那么S*呢就是所有的由终结符所构成的大大小小的字符串的所有的集合。
那么L呢是S*的一个子集，那么也就表示了L它是一个语言，
那么它说L是一个正则集合， 那正则集合呢那它肯定就会对应某一个正则表达式对吧？
那么正则集合呢当且仅当说对于某一个正则语法G来说， 有这个L=L(G)。
这个L(G)呢是由 正则语法所产生的语言，那么这个L呢是正则表达式
所对应的正则集合。
那这个定理呢就把它们这两者建立了一个一一对应的关系。
它所以它是用当且仅当，对吧？那我们在接下来呢
试图来说明一下，并不是严格地证明，说明一下它为什么可以这样？
那实际上呢我们可以从这个正则语法G所构造
构造出对应的正则集合和它的这个正则表达式，也就是说我有了这个正则语法，
我可以把这个语法构造出这个正则表达式来的话，那么它不就建立了一个一一对应的关系了嘛？
那么好，我们就把这个G的这个语法，它不是有产生式，
那么产生式呢都可以表达式为这个语法图，它可以用语法图的形式来表达。
那么刚刚我们也发现了语法图呢它可以进行化简，
那所谓的化简呢，就可以把几个图合并成一个大图， 那么再把所有的产生式通通都合并了以后，
这个大图里边只包含什么呢？只包含v0这么一个非终结符，也就是它的一个替换的一个起点。
那么对于，那么其他所有的全都是圆框，没有一个方框。
那么其他所有的都是终结符，那么我们就把这样的图叫做 主导图，叫做master diagram，叫做主导图。
那么接下来呢我们说这个语法图，语法图当中这个终结符
就对应这个正则表达式当中的终结符，它们字符都是一样的嘛。
现在的我们说如何把这个由 语法产生式最后呢经过对应到
语法图，然后经过化简，经过合并，变成了一个大图，主导图。
如何把它翻译成正则表达式呢？我们就来分析这个 主导图它的结构，对它的结构进行分析。
那么结构呢也正是这三大结构，一个是串联的结构。
那么也就是说它会是一个串联子图，当然我们看到有一群的一个图，
另外一群的图它们是一个串联关系的话，那么这就是一个串联子图。
那每一个子图，比如一个子图叫D1，一个子图是D2，那么D1，D2它可能都里面会包含- 很多更复杂的
那么只要是大致是这么一个大的结构的话， 我们就把它对应这个子表达式是α1α2.。
D1所对应的是α1，D2所对应的是α2。
那么这个呢就是一个正则表达式的 一个中间的一个定义了。
如果它 分析出来是一个并联方式，D1，D2呢是可选的，好
我们对应这个正则表达式的子表达式呢就是α1|α2。
那么我们在正则表达式的定义里面呢是有|这么一个的。
如果我们发现了一个回路的子图，它是一个不同的循环的话，
那么我们就对应的这个子表达式是α*， α*，然后呢再对这个每一个子图里面，
再嵌套地去分析是串联，还是并联，还是回路。
那么最终呢就能够得到这个完整的一个正则 表达式了，而这个正则表达式里头只包含有这个终结符。
所以这个呢是一个大致的一个过程，那么这个过程具体怎么做，我们来看看一个例子。
先看这个最上面这个例子，那我们最上面也是a,b,c，然后有个循环。
我们首先分析呢它是一个分支，是一个并联结构，对吧？
所以呢它会用竖杠隔开，然后呢有a竖杠，b然后再竖杠。
然后在第三个分支，我们发现了一个回路结构，所以呢就是c*，所以最终呢它得到了一个
正则表达式，就是a|b|c*。
那么第二个图， 我们首先呢看到它是一个串联的，
那么就是三个结构的串联，由并联结构和单个的终结符，以及一个回路结构的串联。
那么很明显地，就是变成了（a|b）这样的一个并联结构。
串联上c，然后在串联上d*这么一个回路结构，所以呢它也
这样的一个主导图也直接翻译成正则表达式了。
那么第三个呢它就大的结构，第一层次就是一个回路，所以呢最外面它是应该是一个*。
然后里边呢它是一个并联的分支， 那么里边呢应该是一个树干，那树干呢就是a树干上bc，
所以呢最终翻译成这个正则表达式，它就应该是（a|bc）， 然后呢最外面再加一个*。
这样呢我们通过这么一个几个例子， 以及这个对于主导图结构的分析，
我们就让这个正则表达式所对应的这个正则集
和这个正则文法所对应的这个正则语言，它们之间建立了一个 等价的一个关系。
那好，我们从现在开始呢，我们就知道 所有带正则的东西，它们都是一回事。
陈斌副教授
