L もその補数も無限の正規部分集合を持たないように言語 L を設計しますか?

Question

私はオートマトン理論の授業を受けており、現在ポンピング補題を学んでいます。「L もその補集合も無限の正則部分集合をもたないように言語 L を設計する」という演習問題があります。しかし、私は質問を理解していません。無限の正規サブセットとは何ですか?この要件を満たす言語を見つけるにはどうすればよいでしょうか?

誰かこの質問に光を当てられますか？

ありがとう！

Answer 1

より正確には、言語を見つける必要があります L のサブセットがないように L それは無限の正規言語であり、の補完のサブセットはありません L それは無限の正規言語です。

これが間違った例です： L =の結合 a^n と a^n b^n. 。以来 a^n 通常の言語であり、それはのサブセットです L, 、これは答えのために機能しません。

見つけるため L それが要件を満たしているので、これらの種類の質問はパズルのようなものであることがわかりました。あなたはいくつかのことを試して、彼らが働いているかどうかを確認し、彼らが問題を解決しない理由を考えようとします。最終的にあなたは状況の周りにあなたの心をつかみ、解決策を思いつきます。

Answer 2

そうですね、言語の無限の規則的なサブセットは、無限で規則的なサブセットです。まあ、それはあまり役に立たないかもしれません。

したがって、「サブセット」は非常に明確です。

「正規のサブセット」とは、決定論的な有限状態マシンによって受け入れられるものです (実際、言語理論には、この条件が他のいくつかの条件と同等であるという驚くべき定理があります)。

「無限集合」とは、有限ではない集合、または同様に、無限に多くの要素を含む集合です。

言語だとしましょう L 無限の正規サブセットを持つ場合は特別です。

言語を見つけるのはあなたの仕事です L 両方とも L そしてその補足 L 特別なものではありません。

この問題を解決するには、まずその定義を理解する必要があります。メモやテキストから言語の例をいくつか取り上げます。それらが定期的かどうかを確認します。そうでないものが見つかった場合は、それが規則的でない理由を考え、その無限のサブセットすべてが規則的ではないという特性を持つ言語を設計するかどうかを確認してください。次に、その補数を調べたときに何が起こるかを見てみましょう。

直感を養う必要があり、そのための唯一の方法は自分の手を汚すことです。