proof - 为正则语言抽取引理

Question

我在一个相当困难的问题上遇到了一些麻烦。我被要求证明语言 {0^n 1^m 0^n | m,n >= 0} 使用抽水引理是不规则的。在我见过的所有例子中，语言只被提升到同一个变量（即a^nb^n）。所以我的问题是，如何选择合适的字符串来测试这种语言是否不规则？

对该问题的后续跟进是，一旦我有了我的字符串，你如何将字符串分解为 xyz where |xy| 的形式 <= 泵送长度和 |y| >=1？

Answer 1

在您之前看到的示例中，有不同的字母：n 后跟 bs。在给定的示例中，单词的开头和结尾都有 n 个 Os。该语言在这些 Os 块之间添加了 0 个或多个 1。

抽水引理中的 W 分解为 w = xyz 与 |xy| <= m 和 |y| > 0，其中 m 是泵送长度。选择 aw 的方法和以前一样：选择它，使 xy 完全位于由一个字母组成的块内。因为选择了 L 中的 a^nb^na 单词，所以 xy 将完全由 as 组成，这样如果它被“泵送”，那么 as 将多于 bs。因此，您至少需要 m as 并且该词使用的语言意味着您需要选择 m bs。最短的是 w = a^mb^m。对于新的麻烦语言，在这个 L 中选择一个单词，使得 xy 完全由 Os（在第一个块中）组成，这样如果它被“泵送”，那么第一个块中的 Os 将比最后一个块多 - 并且中间的 1 数量没有改变。然而，在语言中，这意味着没有矛盾，因此不能证明 L 是不规则的。