正則語言和抽詞引用

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塊中抽離開的語言。