1

次の言語が正則でないことを Pumping Lemma で証明しようとしています。しかし、私がそれを正しく行ったかどうかは本当にわかりません。

{L = a 2 n | n>= 0}

これまでに行ったことは次のとおりです。

s = a 2 p

x = a 2 i

y = a 2 j

z = a 2 p-ij

したがって、xy 2 z = a 2 p+j

これは、 a 2 p+j > a 2 p であることを意味し、言語は規則的ではなくなります

私はそれを正しくやっていますか？それとも私が間違っていることがありますか？

4

1 に答える 1

5

そうではありませんが、あなたは正しい結論を導き出していますが、その理由付けは少しずれています。Pumping lemmaは、すべての通常の言語について、次の条件が保持される場所として、それ以上の長さのすべての文字列を書くことができるL整数が存在すると述べています。p >= 1sps = xyz

  1. y空でない
  2. xy ≤ p の長さ
  3. xy i z はLすべての i ≥ 0 の言語です

あなたの最初のステップは正しいです。s = a 2 pは確かに p よりも長いです。s = xyzしかし、ポンピング補題は、上記の条件を満たすとして s を分割できると述べています。言い換えると、s as の除算が存在s = xyzしますが、上記の 3 つのプロパティを満たす必要があることを知る以外に、その除算が何であるかを選択することはできません。

あなたの場合L、a の数が 2 の累乗である a だけで構成される言語です。 s = a 2 pLを取ると、次に長い文字列は (a 2 p ) 2であることがわかります。i = 2そこから、最初の 2 つの条件が成立する場合、a 2 p < xy 2 z < (a 2 p ) 2であるため、3 番目の条件は確実に について成立しないことがわかります。(平易な英語では、xy 2 zの長さは2の累乗の間なのでL、通常の言語の場合とは異なります)

于 2013-02-07T18:42:35.280 に答える