私はオートマトン理論の授業を受けており、今はポンピング補題を学んでいます。「L もその補集合も無限の正規部分集合を持たないように言語 L を設計しますか?」という演習問題があります。しかし、私は質問を理解していません。無限正部分集合とは? この要件を満たす言語を見つけるにはどうすればよいですか?
誰でもこの質問に光を当てることができますか?
ありがとう！
1596 次
2 に答える
0
より正確には、無限正規言語であるサブセットがないように、また無限正規言語である補集合のサブセットがLないように、言語を見つける必要があります。LL
これは間違った例です: =とLの結合。は通常の言語であり、 のサブセットであるため、これは答えとしては機能しません。a^na^n b^na^nL
L要件を満たすを見つけるには、この種の質問はパズルに似ていることがわかりました。いくつかのことを試して、うまくいくかどうかを確認し、なぜ問題が解決しないのかを考えてみます。最終的には状況を把握し、解決策を考え出します。
于 2011-01-22T04:05:41.637 に答える
0
さて、言語の無限規則サブセットは、無限かつ規則的なサブセットです。わかりました、それはおそらくあまり役に立ちません。
したがって、「サブセット」は非常に明確です。
「通常のサブセット」とは、決定論的な有限状態マシンによって受け入れられるものです (言語の理論には、この条件が他のいくつかの条件と同等であるという驚くべき定理が実際にあります)。
「無限集合」とは、有限でない集合、または同等に、無限に多くの要素を持つ集合です。
Lですから、無限の規則的な部分集合を持つ言語は特別であるとしましょう。
L両方Lと補数Lが特別ではないような言語を見つけるのはあなたの仕事です。
この問題を解決するには、まずその定義に頭を悩ませる必要があります。あなたのメモやテキストから言語の例をいくつか取り上げてください。それらが規則的かどうかを調べます。そうでないものを見つけた場合は、それが規則的ではない理由を考え、無限部分集合のすべてが規則的ではないという特性を持つ言語を設計するかどうかを確認してください。次に、その補数を見るとどうなるかを見てください。
直感を構築する必要があり、そのための唯一の方法は手を汚すことです。
于 2011-01-22T04:07:51.383 に答える