automata - (00+1)* 的逆同态

Question

我发现了正则表达式 (00+1)* 的逆同态的一个例子（在 'Hopcroft, Motwani, ullman' 书的第 131 页）。

如果 h(a)=01 和 h(b)=10，那么作者说给定正则表达式的逆同态是正则表达式 (ba)*。

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

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

Answer 1

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

该图像包含所有在 (00+1)* 中具有图片的字符串。正如您正确观察的那样，00 和 1 没有图片。因此他们不贡献任何东西。这就是逆态射与非逆态射的不同之处。决定性的事实是所有确实有贡献的字符串都贡献了来自 (ba)* 的字符串。