TIN 13. Konečné automaty

Card Set Information

Author:
hrbi
ID:
222581
Filename:
TIN 13. Konečné automaty
Updated:
2013-06-05 16:19:24
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ý konečný automat
    • petice M = (Q, Σ, δ, q0, F):
    • Q konečná množina stavů
    • Σ konečná vstupní abeceda
    • δ: Q×Σ → 2Q
    • q0 ∈ Q počáteční stav
    • F ⊆ Q množina koncových stavů
  2. Deterministický konečný automat
    • δ: Q×Σ → Q ∪ {nedef}, nedef ∉ Q
    • nebo parciální δ: Q×Σ → Q
  3. Rozšířený konečný automat
    δ: Q×(Σ∪{ε}) → 2Q
  4. Konfigurace KA
    • C = (q, w), q ∈ Q, w ∈ Σ*
    • počáteční: (q0, a1a2...an)
    • koncová: (qF, ε), qF ∈ F
  5. Přechod automatu
    • relace ⊢M ⊆ (Q×Σ*)×(Q×Σ*)
    • (q, w) ⊢M (q', w') :⇔ w = aw' ∧ q' ∈ δ(q, a)
  6. Řetězec přijímaný KA
    (q0, w) ⊢M* (qF, ε), qF ∈ F
  7. Jazyk přijímany KA
    L(M) = {w | (q0, w) ⊢M* (qF, ε), qF ∈ F}
  8. Převod NKA na DKA
    • 1. Q' := 2Q
    • 2. q0' := {q0'}
    • 3. F' := {S | S ∈ 2Q ∧ S ∩ F ≠ Ø}
    • 4. δ'(S, a) = ∪δ(q, a), q ∈ S, je-li ∪δ(q, a) ≠ Ø, jinak nedef
  9. Převod lineární gramatiky na NKA
    • G = (N, Σ, P, S)
    • vyžaduje tvar gramatiky: A → aB, A → ε
    • M = (Q, Σ, δ, q0, F)
    • 1. Q := N
    • 2. Σ := v
    • 3. δ: δ(A, a) obsahuje B, pokud A → aB ∈ P
    • 4. q0 := S
    • 5. F = {A | A → ε ∈ P}
  10. Převod NKA na lineární gramatiku
    • M = (Q, Σ, δ, q0, F)
    • G = (Q, Σ, P, q0)
    • 1. r ∈ δ(q, a) ⇒ q → ar ∈ P
    • 2. p ∈ F ⇒ p → ε ∈ P
  11. Dosažitelný stav KA
    • M = (Q, Σ, δ, q0, F)
    • q je dosažitelný ⇔ ∃w ∈ Σ*: (q0, w) ⊢M* (q, ε)
  12. Eliminace nedosažitelných stavů
    • M = (Q, Σ, δ, q0, F)
    • 1. vyjdeme z počátečního stavu, Q' = {q0}
    • 2. přidáme do Q' všechny stavy, kam vede hrana z nějakého stavu v Q'
    • 3. opakujeme 2, dokud nepřibude žádný nový stav
  13. Jazykově nerozlišitelné stavy
    • M = (Q, Σ, δ, q0, F)
    • w ∈ Σ* rozlišuje stavy q1, q2 ⇔ (q1, w) ⊢M* (q3, ε) ∧ (q2, w) ⊢M* (q4, ε) ∧ právě jeden ze stavů q3, q4 je koncový
  14. k-nerozlišitelné stavy
    • M = (Q, Σ, δ, q0, F)
    • q1, q2 jsou k-nerozlišitelné ⇔ neexistuje řetězec w ∈ Σ*, |w| ≤ k, který je rozlišuje
  15. Úplný DKA
    obsahuje přechod pro každý symbol abecedy z každého stavu
  16. Redukovaný DKA
    úplný DKA, který neobsahuje nedostupné stavy a nerozlišitelné stavy
  17. Minimalizace DKA
    • 1. odstranění nedostupných stavů
    • 2. zúplnění
    • 3. vytvoření relace ekvivalence 0-rozlišitelnosti (rozdělení stavů na 2 třídy - koncové a nekoncové stavy)
    • 4. vytvoření relace ekvivalence k-rozlišitelnosti (pokud ve třídě existují stavy, které jsou rozlišitelné, tj. pro libovolný symbol jdou do různých tříd, rozdělím třídu)
    • 5. pokud relace k-rozlišitelnosti je stejná jako (k-1)-rozlišitelnosti, končím
    • 6. nové stavy odpovídají získaným třídám
    • 7. vytvoření přechodové fce
  18. ε-uzávěr
    • ε-uzávěr stavu q je množina všech stavů, kam se lze dostat pouze ε přechody
    • ε-uzávěr(q) = {p | ∃w ∈ Σ*: (q, w) ⊢M* (p, w)}
    • ε-uzávěr funguje i na množinu, pak je to sjednocení ε-uzávěrů pro jednotlivé stavy v té množině
  19. Převod rozšířeného KA na DKA
    • 1. nový počáteční stav je ε-uzávěr původního
    • 2. přechody konstruuju tak, že vezmu ε-uzávěr stavu najdu všechny stavy, kam se dá dostat s daným symbolem a provedu opět ε-uzávěr
    • 3. koncové stavy jsou ty, které obsahují původní koncový stav

What would you like to do?

Home > Flashcards > Print Preview