bài tập chương VI otomat đẩy xuống

Xây dựng PDA chấp nhận các ngôn ngữ :

a) {0^m 1^m 2ⁿ | m, n ≥ 1}

b) {a^k b^l cⁿ d^m | m = k + l + n}

c) {w | w ∈ {a, b}^* và #a(w) = #b(w)}

d) {w | w ∈ {a,b}^* và #a(w) = 2#b(w)}

Xây dựng PDA tương đương với văn phạm :

a) S ® + SS | *SS | a

b) S ® aS | bS | aA

A ® bB| b

B ® aC

C ® b

Xây dựng văn phạm CFG tương đương với các PDA sau :

a) M ({q₀, q₁}, {0, 1}, {Z₀, X}, δ, q₀, Z₀, ∅ size 12{ emptyset } {}), trong đó δ được cho như sau:

d(q₀, 1, Z₀) = {(q₀, XZ₀)}

d(q₀, 0, X) = {(q₀, XX)}

d(q₀, 1, X) = {(q₁, e)}

d(q₁, 1, X) = {(q₁, e)}

d(q₁, e, X) = {(q₁, e)}

d(q₁, e, Z₀) = {(q₁, e)}

b) M ({q₀, q₁}, {0, 1}, {Z₀, X}, δ, q₀, Z₀, ∅ size 12{ emptyset } {}), trong đó δ được cho như sau:

d(q₀, 1, Z₀) = {(q0, XZ₀)}

d(q₀, 1, X) = {(q0, XX)}

d(q₀, 0, X) = {(q₁, X)}

d(q₀, e, Z₀) = {(q₀, e)}

d(q₁, 1, X) = {(q₁, e)}

d(q₁, 0, Z₀) = {(q₀, Z₀)}

c) M ({q₀, q₁}, {a, b, c}, {Z₀, X}, δ, q₀, Z₀, ∅ size 12{ emptyset } {}), trong đó δ được cho như sau:

d(q₀, a, Z₀) = {(q₀, X)}

d(q₀, a, X) = {(q₀, XX)}

d(q₀, c, X) = {(q₁, X)}

d(q₀, b, Z₀) = {(q₀, X)}

d(q₀, b, X) = {(q₀, XX)}

d(q₁, c, X) = {(q₁, e)}