20 - Regulární jazyky a jejich modely

•  pro pochopení látky je třeba mít přehled nad základními pojmy, jsou triviální, přesto je zde pro jistotu uvádím

• Abeceda - konečná a neprázdná množina elementů, keré nazýváme symboly (Σ = {a,b,1,2} … abeceda sigma obsahuje symboly a,b,1,2)

• Řetězec - Nechť Σ je abeceda.
  1. ε je řetězec nad abecedou Σ
  2. pokud x je řetězec nad Σ a a ∈ Σ, potom xa je řetězec nad abecedou Σ
• Vlastnosti a operaci s řetězci … nechť x = 1010
  1. délka - počet znaků … |x| = 4
  2. konkatenace - zřetězení … x.x = 10101010
  3. mocnina - říká nám, kolikrát za sebe zkonkatenujeme řetězec … x³ = 101010101010
  4. reversace - obrátíme řetězec … reversal(x) = 0101
  5. prefix - „předpona“ řetězce - prefix(„1010“) = { ε, 1, 10, 101, 1010 }
  6. sufix - „přípona“ řetězce - sufix(„1010“) = { ε, 0, 10, 010, 1010 }
  7. vlastní prefix/sufix - není obsaženo ε a samotný řetězec
  8. podřetězec - prefix ∪ sufix ∪ vnitřní řetězce
  9. vlastní podřetězec - podřetězec - { ε, celý řetězec }
• Jazyk - Nechť Σ* značí množinu všech řetězců nad Σ. Každá podmnožina L ⊆ Σ* je jazyk nad Σ.
  1. kardinalita - počet všech možných řetězců (slov)
     1. konečný jazyk - má konečnou kardinalitu - např. ∅ , {ε}, {x: |x| = 1}
     2. nekonečný jazyk - má nekonečnou kardinalitu - např. {x: 10 je podřetězec x}

• Operace nad jazyky … nechť L₁ = {0, 1, 00, 01}, L₂ = {00, 01, 10, 11}, L₃ = {0, 01}
  1. sjednocení … L₁ ∪ L₂ = {0, 1, 00, 01, 10, 11}
  2. průnik … L₁ ∩ L₂ = {00, 01}
  3. rozdíl … L₁ – L₂ = {0, 1}
  4. doplněk … L₁' = { 10, 11, 001, 010, … }
  5. konkatenace … L₁.L₂ = { 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, 0011, 0100, 0101, 0010, 0011 }
  6. reversace …reversal L₁ = { 0, 1, 00, 10 }
  7. mocnina … L₃² = { 00, 001, 010, 0101 }
  8. iterace
     1. L^* = L⁰ ∪ L¹ ∪ L² ∪ … ∪ Lⁱ ∪ …
     2. L⁺ = L¹ ∪ L² ∪ … ∪ Lⁱ ∪ …

Sjednocení	Průnik	Rozdíl	Doplněk

Konečný automat (KA) je pětice: M = (Q, Σ, R, s, F), kde:

• Q je konečná množina stavů
• Σ je vstupní abeceda
• R je konečná množina pravidel tvaru: pa → q, kde p, q ∈ Q, a ∈ Σ ∪ {ε}
• s ∈ Q je počáteční stav
• F ⊆ Q je množina koncových stavů

• dá se zobrazit grafem i tabulkou

• další pojmy:
  1. konfigurace - řetězec χ ∈ QΣ* (př. pax, qx, …)
  2. přechod - výpočetní krok KA - hrana mezi dvěma konfiguracemi (př. pax |- qx)
• přijímaný jazyk - Jazyk přijímaný konečným automatem M, L(M), je definován: L(M) = {w: w ∈ Σ^*, sw |–^* f, f ∈ F}
  • máme nějakou posloupnost znaků w (vstup/jazyk), jsme v počátečním stavu w, …, pokud jsme schopni dojít v nějaké konečné posloupnosti do některého z koncových stavů, je tento jazyk přijímaný

•  v praxi je třeba vyřešit problém nedeterminičnosti - pokud KA není deterministický, špatně se programuje
• navrhnout nedeterministický automat je mnohem jednodušší jak deterministický, proto navrhujeme nedeterministický a poté se ho snažíme převést na deterministický

1.  nedeterministický automat
   1. obsahuje ε-přechody … ε-uzávěr stavu je množina stavů, kam až dojdeme bez načtení znaku (přes ε-přechod)
   2. obsahuje více cest pro jeden znak z daného stavu
2. deterministický KA - odstranění předchozích dvou problémů
   1. může obsahovat i 0 cest pro daný znak - dá se vyřešit stavem q_false - nemůže se tedy zaseknout → Úplný DKA
   2. může obsahovat nedostupné stavy a více neukončujících stavů → odstraněním získáme Dobře specifikovaný KA (jeden neukončující stav q_false)
   3. může obsahovat nerozlišitelné stavy (stavy, které jdou sloučit do jednoho)- odstraněním získáme Minimální konečný automat