DFAが同じ言語を受け入れる回数は無制限です

特定の言語のDFAはすべてのDFAのサブセットであるため、DFAはカウント可能であることを認識しています。 DFAの数が特定の言語を受け入れることが無限であることを証明する方法はなんですか？DFAが同じ言語を受け入れる回数は無制限です

2012-02-09 Anonymous

ご使用の言語に対応するDFAを用意してください。他のサイクル/ループを含む必要があります。サイクルに対応する新しい状態セットを追加し、この状態セットがサイクル/ループを通る奇数番号のパスを表すことを可能にする（元の状態は偶数パスを表す）。必要に応じて非決定性を追加し、powerset構造を使用してNFAをDFAに戻します。

いずれにしても、より多くの州を持つ同じ言語のDFAになります。

出典

2012-02-09 03:34:28 Patrick87

すべてのDFAには、有限数の状態がありますが、入力文字列内の遷移数を任意に大きくできる必要があるため、サイクルが必要です。 DFAはクラッシュすることはできません。 n個の状態を持つDFAは、長さn + 1の文字列を処理（受理または拒否）できなければなりません。これは、ある状態が2回訪問されたことを意味します。ここでも、すべてのDFAにはループ/サイクルがあります。「反例」を提出すると、ループ/サイクルがあること、またはDFAではないことが示されます。 – Patrick87

ありがとうございました！ –

ステートマシンがすべて互いに到達可能なN個の状態を持ち、k個のシンボルのアルファベットからの入力を受け入れるが、マシンについて何も知らない場合、最短の入力を計算する方法はあるかすべてのN * k状態遷移に当たることが保証されています（つまり、基準を満たすすべてのステートマシンのすべての状態遷移にヒットします）。 – supercat

DFAが同じ言語を受け入れる回数は無制限です

答えて

関連する問題