この式は決定論的有限自動化によって受け入れられますが、この式にポンピング レンマを適用すると、ポンピング レンマが失敗します。また、この式は有限の状態を持ちますが、停止して継続的に実行されず、エッジは自己ループを b/w で作成し続けます。 i が大きくなる傾向があり、無限大になる傾向がある場合、それは停止するはずがないと述べています。したがって、この式では DFA を描くことができますが、レンマと TM のポンピングは失敗します。では、これが通常の文法かどうか教えてください。
1 に答える
0
実際、DFA を描画することはできません (少なくとも正しいものです)。ポンピング補題が矛盾を与えるのは正しいです。iをポンピングして非正方形にするのは簡単です。ポンピング補題が言語が規則的でないことを示している場合、定義上、その言語を表す DFA を描画する方法はありません。
状態のセットは無限です。a^1 を受け入れる状態が 1 つ、a^2 を受け入れる状態が 1 つ、a^3 を受け入れる状態が 1 つ必要です。次に、これらの受け入れ状態の間にすべての状態があります..かなりすぐに乱雑になります。とにかく、ポンピング補題が言語が規則的でないことを示している場合 (適切に適用していると仮定して)、その言語を表す DFA (または正規表現) はありません。
于 2013-12-14T20:41:30.713 に答える