regular-language - 正则语言和抽取引理

Question

我正在努力解决以下问题。我应该使用抽引引理或常规语言闭包，但我无法为这两个问题提出解决方案。任何见解将不胜感激。谢谢。

对于以下每种语言，证明它是正则的或证明它是非常规的：

1) {a^m b^n c^k: m>n>k}

2) {u that belong to {0,1}^* : u begins with 1001 and does not end with 0010}

当涉及到数字 1 时，我的假设是给定语言的反面也必须是正则的。然后我可以使用抽水引理来证明它不是正则的，因此原始语言是非常规的。这会是一种有效的方法吗？

老实说，我不知道如何接近 2 号。

Answer 1

实际上2）很简单。长度为 8 或更长的单词的正则表达式是

1001 · {0,1}^* · {all words of length 4 except 0010}

然后你想到所有满足定义的短词并取并集。

对于 1) 如果您知道反转下的闭合，请使用此和泵引引理。反转将 c^k 带到前面，如果您在此块内抽水，那么您显然会离开该语言。

否则取补并与 ab^+ c^+ 相交。你得到

{a^m b^n c^k: m=1 AND (m<n OR n<k)}

这是

{a b^n c^k: n<k }.

现在您可以在 b 块内抽出以离开该语言。