2

言語は { A n B (2n) C n | ここで n>=0 }

A をプッシュ、B をプッシュ、C がスタックから 3 回ポップされるたびに、C がなくスタックが空の場合は true を返し、それ以外の場合は false を返します。

4

2 に答える 2

4

Use the pumping lemma to prove this is not a context-free language.

Consider s = ap b2p cp
Then we consider vxy, |vxy|<=p, |vy|>0 and uvixyiz in L
We have the possibilities

  1. vxy = aj, j<=p
  2. vxy = aj bk, j+k<=p
  3. vxy = bj, j<=p
  4. vxy = bj ck, j+k<=p
  5. vxy = cj, j <=p

In any case, there are no constants u and v s.t. the string is in L, because there can only be two symbols in vxy and we would then need a variable amount of the third to show in up u or v

Your proposed automata fails on AAAC, returning true. It doesn't guarantee that you have twice as many B's as A's.

于 2013-05-10T22:48:15.727 に答える
3

この言語は文脈自由ではないため、そのような PDA は存在しません。これを簡単に証明します。これは、文脈自由言語が逆準同型の下で閉じているという事実に依存しています (これらのスライドで述べたように)。

言語 L = { A n B 2n C n | n in N } から定義された準同型 h を考えます。

  • h(A) = A
  • h(B) = BB
  • h(C) = C

L に適用されるこの準同型の逆は、言語 h -1 (L) = { x in Σ* | です。h(x) ∈ L }. h の選択を見てみると、これは言語 { A n B n C n | N 中の n }。この言語は、非文脈自由言語の標準的な例です。ただし、CFL は逆準同型の下で閉じているため、h -1 (L) は文脈自由ではないため、L は文脈自由ではありません。したがって、そのための PDA はありません。

お役に立てれば！

于 2013-05-10T22:59:51.290 に答える