正则语言和抽词引用

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）如果你知道倒转时的封闭，使用这个和抽水引理。反转需要在前面，如果你在这个块内抽水，你显然会离开语言。

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

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

这是

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

现在你可以在B块中抽离开的语言。