0

これはこれの繰り返しですが、私はPDAの設計に関して話します。

これはよく知られている例であるため、私は間違っていることを知っていますが、以下のPDA設計でどこが間違っていたのでしょうか。

言語を受け入れたい{a^n b^n c^n: n>=0}

1に遭遇するたびにスタックに2つプッシュしa、1つをポップし、1つをbポップしcて、スタックが空かどうかを確認します。遷移関数（最小）を次のように定義しました：

(q0, a, Z) = (q0, 11Z)
(q0, a, 1) = (q0, 111)
(q0, b, 1) = (q1, delta)
(q1, c, 1) = (q2, delta)
(q2, delta, Z) = (q-Final, Z) (epsilon move)

Z is empty stack

このPDAはそのような言語を受け入れませんか？

4

1 に答える 1

1

PDA は次の言語を受け入れます。

{a^n b^i c^j; n >= 0 and i + j = 2n}

{a^n b^n c^n: n>=0}上記の言語のサブセットであると同じではありません。具体的にはi = nとの場合j = nです。

于 2013-01-15T18:26:15.580 に答える