Video在线视频

欢迎同学们来到《软件理论基础》的MOOC课堂

现在介绍正则表示的第五节

就是正则语言的同态

前面我们介绍了正则语言

它的并运算 连接运算 交运算 补运算等等

都是封闭的

特别是它的连接运算是封闭的

那现在我们讲一个更一般的结论

就是正则语言它的同态运算它的性质

那首先我们定义它的同态

对一个输入字母∑和另外一个输入字母T

那∑到T的*闭包映射h

定义为对于它的一个输入字母

对应T上面一个串

我们定义了这个映射之后

然后在∑上面的每一个串w

这个w这个字符串

我们定义w是在h下面的一个映射

实际上是对每一个输入字母

它的映射的像做连接

这样得到的当然是T*上面的一个字符串了

根据我们第一章介绍的内容

我们知道这样定义的映射h

一定是∑到T*上面的一个同态

这是同学们可以在底下去验证的

那我们定义了这个对于单个字母对串

那我们在接着定义对一个语言

∑上面的一个语言

这个语言上面都包含的是字符串

对每一个字符串

我们都是按这种映射来产生的

那这样得到语言上面的

一个映射的一个集合 h（L）

这就是语言的像

这也是语言上面的一个同态了

下面我们看个例子

假设h它等于0

它映射的是ab这个串

对于1映射是空串

那我们看h对这个串0101

根据定义它应该是h（0），h（1），h（0），h（1）这些连接

那根据映射的像，带进去就得到就是abab

这个同态就是这样作用的

下面我们再看给一个语言

是∑上面的一个语言

这个语言是0的k次方 1的k次方

每一个串也就是0的k次方 1的k次方

这个串在h下面它的作用像

h（0）的k次方 1的k次方

那根据刚才我们定义的这个串的这个映射

实际上可以得到的是（ab）的k次方

这个ka是任意的

实际上也就是ab的*闭包

那这个语言经过h它的映射

就得到ab*的这个语言

这个例子告诉我们

给了一个语言在同态映射h下

它可以生成另外一个语言

那如果是我们给了这个语言是正则语言

那在这个同态映射下

它的项是什么语言呢

这就是我们下面要介绍的定理

假设L是正则语言

给的同态h

在h这个映射下

它的像也是正则语言

那我们要证明这个定理

我们就要用到刚才讲的正则表示

与正则语言之间的关系

因为我们证明了正则表示的语言

就是正则语言

那给了一个正则语言

一定有一个正则表示

它的语言

就是你给定这个语言 正则语言

下面我们通过这个结论

给了L是正则语言

它对应的正则表示是E

那下面我们要证明的是正则表示E

它的项也是正则表示

还有这个h（E）这个正则表示

它的语言

跟1这个语言

1这个正则表示的语言

它的项是相等的

就是跟我们给定这个语言

它的项是一致的

这里面我们需要说明的是h（E）

是怎么定义的

因为我们定义了h是∑T*上面的一个变换

那h（E）实际上是把这个h（a）这个符号a

换成为它的正则表示a就可以了

实际上就是这个映射

它的功能跟我们原来的是类似的

或者是一致的

那下面我们要证明这两件事

第一个是正则表示

它的项是正则表示

正则表示它的像与语言之间

它可以互换

我们要证明这个

我们就通过正则表示它的定义来证明

也就是我们的正则表示

是通过归纳来定义的

我们对E的它的结构要做归纳来证明

如果是1是我们基本的正则表示

也就是我们的空串和空集

我们就可以通过刚才的

我们说明了这个

这个空串或者空集它的像

依然是空串或者空集

这个我们可以去检验它

所以它们的项依然是正则表示

并且这个结论是显然成立的

那对单个的输入字母呢

我们也可以检验

因为这个得到的依然是正则表示

而且它们的语言是肯定都

这个调换之后都是相同的

所以对基础的正则表示

这个结论1和2是成立的

那假设对E1、E2两个正则表示

它们的像 h（E1）、h（E2）

如果也是正则表示

而且也满足这个关系式

这是我们的归纳假设

那我们要证明的是结论1和结论2

根据定义我们很容易检验这个h1

因为1是等于E1连接E2的

那根据刚才h实际上是把那个输入字母a

换成正则表示a

所以我们在根据h的同态的性质

我们很容易检验了这个h（E）

实际上是等于h（E1）连接h（E2）

那根据刚才的假设

h（E）它的语言就可以写成为

这两个映射的连接它的语言

再根据

因为这两个我们假设的都是正则表示

那它的语言就根据这两个语言的连接

再根据归纳假设

这个正则表示的语言

可以根据它的语言的这个像是相等的

这个是跟这个式子相等的

所以整个这个式子就等于它

然后我们再根据这个同态的性质

这个关系式就等于这个关系式

再根据正则表示的语言

这里面它们两个语言的连接

实际上就等于两个正则表示连接的语言

它跟它相等

最后也就是等于这个关系式

这样我们就验证了第二个式子

同样我们还可以检验

这个正则表示的+和*运算等等

这样我们就证明了

正则表示它的对应语言

一定在这个同态下是正则语言

也就是正则语言在同态映射下面

它的项依然是正则语言

下面我们再讨论正则语言的逆同态

那什么是逆同态

给了这个映射h

就是我们之前定义的从∑到T*

你看那个定义的它是一个同态映射

不是考虑∑*上面的语言

我们是考虑它下级T*上面的语言

而如果是T*上面的语言

它的原项也就是W是∑*上面的串

w它做这个h映射下面的项

是摄入我们L里面的

在这种情况下我们求出的这个w

实际上是这个L语言的在∑上面的原项

那我们考虑这个原像它的这个语言

我们下面有这么一个定理

如果L是这个下级上面的正则语言

在这个同态下面 L的原项

它也是正则语言

那我们要验证它

就通过构造它的原项的自动机

怎么构造呢

假设L是正则语言

那它一定有一个DFA

来接受这个语言L

我们假设DFA是A

我们通过这个DFA来构造L的逆向

这个构造呢

就是我们得到的自动机是b

这个b的状态跟a的状态

实际上是一样的

初态也是一样的 终态也是一样的

只是输入字母这里是∑

而状态转移函数 我们是再定义的

这个状态转移函数

就是b上面的状态转移函数

对于任何状态q我输入一个a

实际上它的转移

是我们的自动机a上面

在状态q 输入一个字符串h（a）

h（a）实际上是我们讲的同态的一个项

a的同态

那这样得到的实际上是一个扩展的状态转移

是a这个自动机里面的一个扩展的状态转移

但是它的b这个转移

因为这个转移 它是这样定义的

通过这个图

大家可以看出

这是原来的T中的自动机就是a

那我要构造另外的自动机

初始状态跟原来的这个初始状态是一样的

只是我的输入字母这里面

是经过了这一个同态的h

做了一个变换 然后到这里面来

那这样如果是按a中的自动机

这个串被接受

那我们这个b中的自动机也是接受的

如果a中是拒绝的

那b中拒绝

那这样我们实际上就得到

对于从初态开始任何一个串

它的接受或者拒绝

都是根据a来判定的

这里就得到了∑上面的这个DFA这个自动机

那也就是原来语言L的

一个逆向的一个自动机

那当然这个逆向就是一个正则语言了

这样我们就证明了

正则语言的逆同态依然是正则语言

那实际上我们在这节里面

就证明了正则语言在同态下面是封闭的

在逆同态下面它也是封闭的

好 我们这节介绍完毕

谢谢大家