(00+1)*的逆同态

Question

我发现了正则表达式的逆同态(00+1)* (在'Hopcroft，Motwani，ullman‘书的第131号页上)。

如果h(a)=01，h(b)=10，则指出给定正则表达式的逆同态是正则表达式(ba)*。

但是(00+1)*语言中有字符串00和1，不能用(ba)*语言中的任何字符串表示。

这个例子是错的，还是我想错了方向？

Answer 1

在(00+1)*中表示字符串的不是语言(ba)*中的字符串，而是相反的方式。从(ba)*的字母表映射到(00+1)*字母表上的字符串。因此，逆同态映射正好相反。

图像包含在(00+1)*中有图片的所有字符串。正如您正确观察到的，00和1没有图片。因此，他们没有作出任何贡献。这就是反态射与非逆态射的区别。决定性的事实是，所有确实贡献的字符串都来自(ba)*。