TIN 16. Zásobníkové automaty

Card Set Information

Author:
hrbi
ID:
222657
Filename:
TIN 16. Zásobníkové automaty
Updated:
2013-06-06 10:33:28
Tags:
tin
Folders:

Description:
mssz 2013
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user hrbi on FreezingBlue Flashcards. What would you like to do?


  1. Nedeterministický ZA
    • P = (Q, Σ, Γ, δ, q0, Z0, F)
    • Q konečná množina stavů
    • Σ konečná vstupní abeceda
    • Γ konečná pásková abeceda
    • δ: Q×(Σ∪{ε})×Γ → 2Q×Γ*
    • q0 ∈ Q počáteční stav
    • Z0 startovací symbol na zásobníku
    • F ⊆ Q množina koncových stavů
  2. Rozšířený ZA
    • δ: Q×(Σ∪{ε})×Γ* → 2Q×Γ*
    • ekvivalentní s NZA
  3. Deterministický ZA
    ∀a ∈ Σ: |δ(q, a, z)| + |δ(q, ε, z)| ≤ 1
  4. Deterministický rozšířený ZA
    • rozšířený ZA
    • ∀q ∈ Q ∀a ∈ Σ∪{ε} ∀γ ∈ Γ*: |δ(q, a, γ)| ≤ 1
    • δ(q, a, α) ≠ Ø ∧ (δ(q, a, β) ≠ Ø ∨ δ(q, ε, β) ≠ Ø) ⇒ α není prefix β a naopak
  5. Konfigurace ZA
    C = (q, w, α), q ∈ Q, w ∈ Σ*, α ∈ Γ*
  6. Přechod ZA
    • relace ⊢P ⊆ (Q×Σ*×Γ*)×(Q×Σ*×Γ*)
    • (q, aw, Zβ) ⊢P (q', w, αβ) :⇔ (q', α) ∈ δ(q, a, Z)
  7. Jazyk přijímaný ZA
    • řetězec přijímaný TS:
    • přechodem do koncového stavu: (q0, w, Z0) ⊢P* (qF, ε, γ), kde qF ∈ F ∧ γ ∈ Γ*
    • vyprázdněním zásobníku: (q0, w, Z0) ⊢P* (q, ε, ε), kde q ∈ Q
    • oboje: (q0, w, Z0) ⊢P* (qF, ε, ε), kde qF ∈ F
    • jazyk přijímaný ZA
    • L(P) = {w | w je přijímaný ZA P}
  8. Převod BKG na RZA
    • G = (N, Σ, P, S)
    • P = ({q, r}, Σ, N∪Σ∪{#}, δ, q, #, {r})
    • 1. redukce: A → α ∈ P ⇒ (q, A) ∈ δ(q, ε, α)
    • 2. shift: ∀a ∈ Σ: δ(q, a, ε) = {(q, a)}
    • 3. ukončení: δ(q, ε, S#) = {(r, ε)}
  9. Neekvivalence NZA a DZA
    • L = {wwR | w ∈ Σ+}
    • DZA nemůže uhádnout, kde končí w a kde začíná wR

What would you like to do?

Home > Flashcards > Print Preview