Zásobníkové automaty – příklady k procvičení
Příklad 1
Mějme zásobníkový automat M = ({q0, qa, qb, qc}, {a, b, c}, {Z, A}, δ, q0, Z, ∅) akceptující prázdným
zásobníkem, kde přechodová funkce δ je definována pomocí následující tabulky:
(stav, zásobník) a b c ε
(q0, Z) (qa, AZ) – – (q0, ε)
(qa, A) (qa, AA) (qb, ε) (qc, ε) –
(qb, A) – (qb, ε) (qc, ε) –
(qc, A) – – (qc, ε) –
(qb, Z) – – – (qb, ε)
(qc, Z) – – – (qc, ε)
Úkoly:
1. Zapište výpočet automatu M na slovech aabc, aaabcc, aaaabbbc.
2. Vypište všechna slova délka maximálně 3, která automat M akceptuje.
3. Vypište všechna slova délka maximálně 3, která automat M neakceptuje.
4. Určete jazyk L = L(M).
Příklad 2
Mějme následující zásobníkový automat M = ({q0, q1, q2, qf }, {a, b, c}, {Z, A, D}), δ, q0, Z, {qf })
akceptující koncovým stavem, kde přechodová funkce δ je definována takto:
δ(q0, a, Z) = (q1, DZ) δ(q0, b, Z) = (q0, Z) δ(q0, c, Z) = (q2, Z)
δ(q1, a, D) = (q1, AD) δ(q1, b, D) = (q1, D) δ(q1, c, D) = (qf , D)
δ(q1, a, A) = (q1, AA) δ(q1, b, A) = (q1, A) δ(q1, c, A) = (qf , A)
δ(qf , a, A) = (qf , ε) δ(qf , b, A) = (qf , A)
δ(qf , a, D) = (q2, ε) δ(qf , b, D) = (qf , D)
δ(q2, a, Z) = (qf , ε) δ(q2, b, Z) = (q2, Z)
δ(qf , a, ε) = (qf , ε) δ(qf , b, ε) = (qf , ε)
Úkoly:
1. Proveďte výpočet automatu M na slovech abcbaa, abaacbab, aabcaaa.
2. Patří slova aca, acaa, abcab, bcb, ab, acb do jazyka L(M)?
3. Určete jazyk L(M). [Nápověda: všimněte si, u jakého symbolu se mění stav zásobníku.]
1
Příklad 3
Sestrojte zásobníkové automaty pro následující jazyky.
1. L1 = {ai
bj
| i = j},
2. L2 = {w.wR
| w ∈ {a, b}∗
},
3. L3 = {an
bn
cm
dm
| m, n ≥ 0},
4. L4 = {am
.w | w ∈ {b, c}∗
, #b(w) = m},
5. L5 = {vcw | v, w ∈ {a, b}∗
, |v| = 2 · |w|}.
2