L をアルファベット {0,1} の文字列で構成される言語とし、1 と 0 を同数含む。
例えば：
000111
10010011
10
1010101010
L が正規言語ではないことをどのように証明できますか?
1314 次
3 に答える
3
{0 ^ n 1 ^ n：n> 0}が正規言語ではないことを示すために使用されるのとまったく同じ引数を使用できると思います。これは、ポンピング補題と矛盾する文字列を自由に選択できるためです。
Lが通常であると仮定します。したがって、整数n（ポンピング長）のポンピング補題を満たす必要があります。S=0^n 1^nLに属する文字列を取ります。見出語によれば、すべての。について、、、およびLに属するようS=xyzに分割できます。ゼロのみで構成されている必要があることに注意してください。ここで、をポンピングすると、文字列にゼロを追加するだけで、Lに属さなくなります。したがって、矛盾があります。したがって、Lは規則的ではありません。|xy| <= n|y|>0x y^i zi>=0yy
于 2012-05-20T12:35:33.800 に答える
1
正式な証明についてはわかりませんが、直観的には、この言語を認識するために DFA を構築することはできないということです (形式111...111000...000などの文字列を追跡するには無制限の数の状態が必要になると考えてください)。
于 2012-05-20T11:33:00.713 に答える
0
形式的な証明は、次のように正規言語のポンピング補題を使用して与えることができます。
言語が規則的であるとします。したがって、const 整数 p のポンピング レンマを満たさなければなりません。0 と 1 の数が等しいs任意の文字列とします。|xy|<=p次に、s は、|y|>0、そしてx(y^i)z、どこi>=0も L に属するように、x、y、z の 3 つの部分に分割できます。
次のように文字列を分割しましょう。
yは、0 と 1 の数が等しくない文字列の一部です。xsbeforeの部分文字列である可能性がありますy。zの後の部分である可能性がありますy。
さて、私が取ることによって文字列を「ポンプダウン」i = 0すると、残りの文字列はxz、言語Lに属さない0と1の数が確実に等しくないものだけになります.
したがって、L が正則であると前に仮定したので、矛盾に達しました。
したがって、それは規則的ではありません。
上記の部分を理解するのが少し難しい場合は、例を考えてみてください。p を整数 50+1000+11101とします。 を L の文字列とします (+ は連結を示します) x を " 0"、y を"1000"、z を残りの部分とし11101ます。次に、 で実行x(y^i)zするとi=0、残りの文字列は011101L の一部ではないことになります。したがって、不規則です。
注: この例は、ロジックを理解するための単なるサンプルです。p の値をランダムに決めることはできません。
于 2012-05-25T13:48:44.207 に答える