infinite - 同じ言語を受け入れるDFAの数は数え切れないほど無限です

Question

特定の言語のDFAはすべてのDFAのサブセットであるため、DFAはカウント可能であることに気付きました。DFAが特定の言語を受け入れる数が無限であることを証明する方法を知りたいですか？

Answer 1

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

いずれにせよ、より多くの状態を持つ同じ言語のDFAになります。