TIN 11. Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.

Card Set Information

Author:
hrbi
ID:
222546
Filename:
TIN 11. Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky.
Updated:
2013-06-06 15:10:52
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. Abeceda
    Σ konečná množina prvků nazývaných symboly
  2. Řetězec
    • Σ abeceda
    • Σ* množina všech konečných posloupností symbolů (řetězců) w = a1a2...an, ai ∈ Σ
    • délka řetězce |w|
    • Σ* obsahuje speciální symbol ε (prázdný řetězec), |ε| = 0
    • |aw| = |w| + 1
  3. Konkatenace řetězců
    • w = a1a2...an, ai ∈ Σ
    • w' = a'1a'2...a'n', a'i ∈ Σ
    • konkatenace ww' = a1a2...ana'1a'2...a'n'
    • 1. |ww'| = |w| + |w'|
    • 2. asociativita
    • 3. wε = εw = w
  4. Jazyk
    • Σ abeceda
    • L ⊆ Σ*
  5. Operace nad jazyky
    • Σ abeceda, jazyk L ⊆ Σ*, L1 ⊆ Σ1*, L2 ⊆ Σ2*
    • komplement: L' = Σ* L
    • součin: L1L2 := {xy | x ∈ L1, y = L2}
    • mocnina: L0 := {ε}, Ln := LLn-1
    • iterace: L* := ∪Ln, n ≥ 0
    • positivní iterace: L+ := ∪Ln, n > 0
  6. Algebra jazyků
    • (2Σ*, ∪, ·, Ø, {ε}) polookruh (kom. monoid + monoid)
    • ∪ sjednocení
    • · konkatenace
  7. Gramatika
    • čtveřice G = (N, Σ, P, S):
    • N konečná množina neterminálních symbolů
    • Σ konečná množina terminálních symbolů
    • P relace, množina přepisovacích pravidel, konečná podmnožina (N ∪ Σ)*N(N ∪ Σ)* × (N ∪ Σ)*
    • S ∈ N výchozí symbol gramatiky
    • prvek (α, β) ∈ P přepisovací pravidlo, zapisuje se ve tvaru α → β (levá → pravá strana)
  8. Přímá derivace
    • relace ⇒ mezi řetězci λ, μ ∈ (N ∪ Σ)*
    • λ⇒μ ⇔ λ = γαδ, μ = γβδ (γ, δ ∈ (N ∪ Σ)*, α → β ∈ P)
  9. Derivace
    • relace ⇒+ je tranzitivní uzávěr relace přímé derivace ⇒
    • ⇒* reflexivní a tranzitivní uzávěr relace ⇒
  10. Větná forma
    α ∈ (N ∪ Σ)* je větná forma, pokud S ⇒* α
  11. Věta
    větná forma složená pouze z terminálů
  12. Jazyk generovaný gramatikou
    L(G) = {w | S ⇒* w ∧ w ∈ Σ*}
  13. Chomského hierarchie
    • pravidla mají tvar:
    • typ 0 (obecné): α → β, α ∈ (N ∪ Σ)*N(N ∪ Σ)*, β ∈ (N ∪ Σ)*
    • typ 1 (kontextové): αAβ → αγβ, A ∈ N α, β ∈ (N ∪ Σ)*, γ ∈ (N ∪ Σ)+ nebo S → ε, pokud S není na pravé straně žádného pravidla
    • typ 2 (bezkontextové): A → α, A ∈ N, α ∈ (N ∪ Σ)*
    • typ 3 (pravé lineární): A → xB nebo A → x, A, B ∈ N, x ∈ Σ*
  14. Typy jazyků
    • jazyk typu 0: rekurzivně vyčíslitelný
    • jazyk typu 1: kontextový
    • jazyk typu 2: bezkontextový
    • jazyk typu 3: regulární
  15. Třídy jazyků
    • rekurzivně spočetný L3
    • rekurzivní
    • kontextový L2
    • bezkontextový L1
    • deterministický bezkontextový
    • regulární L0
    • L3 ⊆ L2 ⊆ L1 ⊆ L0
  16. 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ů
  17. Deterministický konečný automat
    • δ: Q×Σ → Q ∪ {nedef}, nedef ∉ Q
    • nebo parciální δ: Q×Σ → Q
  18. Konfigurace KA
    • C = (q, w), q ∈ Q, w ∈ Σ*
    • počáteční: (q0, a1a2...an)
    • koncová: (qF, ε), qF ∈ F
  19. Přechod KA
    • relace ⊢M ⊆ (Q×Σ*)×(Q×Σ*)
    • (q, w) ⊢M (q', w') :⇔ w = aw' ∧ q' ∈ δ(q, a)
  20. Řetězec přijímaný KA
    (q0, w) ⊢M* (qF, ε), qF ∈ F
  21. Jazyk přijímany KA
    L(M) = {w | (q0, w) ⊢M* (qF, ε), qF ∈ F}
  22. 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
  23. Lineární gramatika
    • pravá: A → xB, A → x
    • levá: A → Bx, A → x
    • lineární: A → xBy, A → x
    • LPL = LLL
    • LPL ⊂ LL
  24. Regulární gramatika
    • pravá: A → aB, A → a, S → ε (pokud S není na pravé straně)
    • levá: A → Ba, A → a, S → ε (pokud S není na pravé straně)

What would you like to do?

Home > Flashcards > Print Preview