关于Hopcroft著作中(00+1)*逆同态示例的合理性疑问

你提到的这个示例并没有错误，问题出在对逆同态定义的理解偏差上，咱们一步步拆解清楚：

先明确核心定义 #

首先得把逆同态的概念掰明白：对于同态 ( h: \Sigma^* \to \Gamma^* )，语言 ( L \subseteq \Gamma^* ) 的逆同态 ( h^{-1}(L) ) 是所有满足 ( h(w) \in L ) 的字符串 ( w \in \Sigma^* )，而不是“能通过h映射得到L中所有元素的w的集合”。

简单说：逆同态只关心哪些w被h映射后落在L里，完全不要求L里的每个元素都能被h映射出来——这是两个完全不同的方向。

回到你的示例 #

咱们对应到书中的例子：

1. 正则表达式 (00+1)* 对应的语言 ( L )：所有由任意数量的00和1拼接成的字符串（比如1、00、100、0011这些都属于L，但01、10这类含单个0的串不属于L）。
2. 同态 ( h(a)=01 )，( h(b)=10 )：把{a,b}上的字符串每个字符替换成对应的二元串，比如 ( h(ba)=h(b)h(a)=1001 )，( h((ba)^2)=10011001 )。

现在看 ( h^{-1}(L) )：

• 对于 ( w=(ba)^n )（n≥0，n=0时是空串）：
  • ( h(w) ) 的结构是 ( (1001)^n )，拆开来就是1+00+1+1+00+1...（n=1时是1+00+1，n=2时是1+00+1+1+00+1），显然每个部分都是00或1，所以 ( h(w) \in L )，因此 ( (ba)^* \subseteq h^{-1}(L) )。
• 反过来，任何不在 ( (ba)^* ) 里的w（比如a、b、ab、aa等）：
  • ( h(a)=01 )，这个串里有单个0，没法拆成00和1的组合，不属于L；
  • ( h(b)=10 )，同样含单个0，不属于L；
  • ( h(ab)=0110 )，还是有单个0，不属于L；
    所有这类w的h(w)都不在L里，所以 ( h^{-1}(L) \subseteq (ba)^* )。

综上，( h^{-1}(L)=(ba)* )，书中的示例是完全正确的。

你的误解点 #

你觉得L里的00、1没法被h映射得到，这一点没错，但这和逆同态的定义无关——逆同态不要求L中的元素都能被h覆盖，只要求找出所有映射后落入L的w。就像你找“所有能通过h变成L中成员的w”，至于L里有没有成员没人能变出来，根本不影响这个集合的定义。

内容的提问来源于stack exchange，提问作者Kavita