DFAと通常の言語

私は次のことについて考えていましたが、答えは肯定的だと思います。DFAと通常の言語

通常のDFA対応言語のすべてのサブセットもDFAで受け入れ可能ですか？

2012-01-22 CyberShot

番号例：アルファベットは、数字数字です。 DFAはすべての自然数を受け入れます。サブセット：DFAはすべての素数を受け入れます。

編集：アルファベットは数字です。申し訳ありませんが、間違った用語があります。

自然数は正規言語として表現することができる（したがって、DFAは、彼らのために構築することができる）：

0|([1-9][0-9]*)

2012-01-22 03:33:16 bdares

実際、あなたが言及している言語のいずれもレギュラーではありません。どちらも無限です。素数の言語はそれを受け入れることができるDFAが存在しないため、規則的ではありません。 – Marcin

@Marcinあなたは、正規表現が '[0-9] *'のような無限の文字列を実際に表現できることを忘れています。 – bdares

いいえ、受け入れることのできる単語の長さに上限がないことを表します。しかし、受け入れられるためには、受諾状態に達しなければならず、その後にはそれ以上の要素はありません。さらに、これは無限のアルファベットを持つことと同じではありません。 – Marcin

すべての有限オートマトン - 決定論だけでなく、非決定的に - することができ通常の言語として表され、その逆もあります。言語のサブセットが標準である場合、はいをDFAとして表すことができます。

2012-01-23 16:10:23

私はこれが質問に答えるとは思わない。問題は、通常の言語のすべてのサブセットも規則的でなければならないかどうかです。これは偽であり、ここで扱われません。 – templatetypedef

ここで重要な点は、通常の言語のサブセットが正規であるとは限りません。 –

答えて