Koncový stav vs. prázdný zásobník – 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, ε)
Převeďte automat M na ekvivalentní automat N přijímající koncovým stavem.
Příklad 2
Mějme následující zásobníkový automat N = ({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 , ε)
Převeďte automat N na ekvivalentní automat M přijímající prázdným zásobníkem.
Příklad 3
Mějme zásobníkový automat M = ({q0, q1}, {0, 1}, {Z0, X}, δ, q0, Z0, ∅) akceptující prázdným
zásobníkem, jehož přechodová funkce δ vypadá takto:
δ(q0, 1, Z0) = (q0, XZ0)
δ(q0, ε, Z0) = (q0, ε)
δ(q0, 1, X) = (q0, XX)
δ(q1, 1, X) = (q1, ε)
δ(q0, 0, X) = (q1, X)
δ(q1, 0, Z0) = (q0, Z0)
Převeďte automat M na ekvivalentní automat N přijímající koncovým stavem.
1
Příklad 4
Mějme zásobníkový automat N = ({q0, qa, qc}, {a, b, c}, {Z, A, C, D}, δ, q0, Z, {qa, qc}), kde δ je
dána tabulkou:
δ a b c
q0Z qaDZ q0Z qcDZ
qaD qaAD qaD q0Z
qaA qaAA qaA qa
qcD q0 qcD qcCD
qcC qc qcC qcCC
Převeďte automat N na ekvivalentní automat M přijímající prázdným zásobníkem.
2