0

以下が通常のセットであるかどうかを述べなければなりません。これらは私の答えです。私が正しいかどうかを知り、私の推論について追加の情報を得たいと思います。また、ポンピング補題を使用せずにこれらを直感的に合理化したいと思います。これは、次のいずれについてもそれほど難しくないと言われています。

一番下の質問を正式に表示するだけです。

   a. {(a^n)(b^m) | n!=m} 
   b. {xcx | x is in {a,b}*}
   c. {xcy | x,y is in {a,b}*}
   d. {(a^n)(b^n+481) | n >= 0}
   e. {(a^n)(b^m) | n>=m and m<= 481}
   f. {(a^n)(b^m) | n>=m and m>= 481}
   h. {(a^n)(b^n)(c^n) | n>=0}


a. Not regular. This would imply that {(a^n)(b^n) | n>=0} is regular, which isn't true either by the closure properties for regular sets.
b. For both b and c, I don't think I am conceptualizing it correctly. Since x can be any arbitrary string of a's or b's, I would say that both parts b and c are not regular. But I don't think that this is correct.
c. See above.
d. Not regular. From the same reasoning from a. Adding a constant really means nothing since n is unbounded positively. 
e. Unsure.
f. Unsure.
h. Not regular from the same reasoning as a.

最後に、{(a^n)(b^n) | の無限部分集合が存在しないことを正式に証明する必要があります。n>=0} サブセットが規則的であるように。

これは、ポンピング補題なしで簡単な方法で行うことができますか? 私は通常のセットについてよく理解していないので、まだ試していません。

4

1 に答える 1

1

ここにいくつかのコメントがあります：

  • (a)については、あなたが正しいと思いますが、その言語が規則的である場合、その理由をどのように正当化するかに注意する必要があります。n in N } は正則です。どのクロージャー プロパティを使用するかを必ず理解してください。

  • (b) については、ヒントとして、準同型を使用します。cを削除できますか？

  • (c) については、この言語が何を意味するかを考えてください。aabaabc言語ですか？caab言語ですか？たとえば、正規表現を使用して、より簡潔に説明する方法を見つけることができますか?

  • (d) については、連結と和集合の下でクロージャを使用することにより、規則的ではないことを証明できます。わかりますか？

  • (e) に​​ついては、言語を { a n | n ≥ 0 } ∪ { a n b | n ≥ 0 } n ≥ 1 } ∪ { a n b 2 } ∪ ... { a n b 471 | n ≥ 1 n≧471}。それは役に立ちますか？

  • (f)については、ヒントとして、規則的ではありません。(e) からの直感を考えると、その理由がわかりますか?

  • (h) については、(b) と同じ手法を使用します。

最後に、最後の質問ですが、実際にここでポンピング補題を使用できます。ポンピング補題の通常の証明では、文字列 a p b pを選択します。ここで、p はポンピング長です。同様のトリックを使用できますが、言語にa p b pがあることを保証することはできません。ただし、 a p +k b p+kは、ある k ≥ 0 の言語でなければならないことを示すことができますか?

お役に立てれば！

于 2013-10-17T23:38:28.303 に答える