正規の言語とポンピング補題

Question

私は次の問題を解決するのに苦労しています。私はポンピング補題や通常の言語クロージャを使うはずですが、私はこれらの2つの問題の解決策を考え出すことはできません。どんな洞察もそれを高く評価します。ありがとう。以下の各言語の

それが規則的であるか、非正規であることを証明することを証明：

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を前面に持ち、このブロック内でポンプを送ると明らかに言語を残します。

それ以外の場合は補数を取り、それをb^+ c^+と交差させます。あなたは

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

今、あなたが言語を残してBブロックの中にポンピングすることができるである

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

を取得します。