IB102-Automaty-a-gramatiky.md

Automaty a gramatiky

---

Přednáška 1 - 17. 09. 2018

Formální jazyk

abeceda

• libovolná konečná množina
• značená symbolem Σ
• např. {a, b, c, d}, {@, #, %, ...}
• prvek abecedy nazýváme jako symbol

slovo (řetězec)

• nad abecedou Σ je libovolná konečná posloupnost znaků této abecedy

  Σ = {a, b, c}
  slova zde budou například:

  • u = abba
  • v = a
  • w = cacacaca
  • y = ε

• prázdnou posloupnost znaků odpovídá prázdné slovo, ozančované jako ε
• počet znaků v posloupnosti v značíme |v|

jazyk

• nad abecedou Σ je libovolná množina slov nad Σ

Σ = {a, b, c}
L = {aa, abac, cc}
L' = {ε}
L''' = prázdná množina

• množina všech slov značíme jako Σ^*
• množinu všech neprázdných slov značíme jako Σ⁺

Operace a relace nad slovy

zřetězení je binární operace, označována . , je definována předpisem: u.v = uv

abac . bb = abacbb
aba . ε = aba
ε . aba = aba

• zřetězení je asociativní, tj. u.(u.w) = (u.v).v

  (ab.bac).ac = abbac.ac = abbacac
  ab.(bac.ac) = ab.bacac = abbacac
  

• není komutativní

podslovo

• u je podslovem v, jestliže existují slova x, y taková, že v = x.u.y
• libovolná podposloupnost daného slova

  v = baca
  podslova: baca, bac, aca, ba, ac, ca, b, a, c, ε

předpona

• pokud je x = ε, tak slovo u je předponou (prefixem)
• pokud je y = ε, tak slovo u nazýváme příponou (suffixem)

mocniny

• unární operace definována pro všechny i
• N₀ = přirozená čísla s 0
• N = přirozená čísla od 1...N

  u⁰ = {ε}
  uⁱ⁺¹ = u.uⁱ

• konkrétní příklad:

  u = ba
  u⁰ = ε
  u¹ = u . u⁰ = ba . ε = ba
  u² = u . u¹ = ba . ba = baba

Operace nad jazyky

• výsledkem je vždy jazyk ∪ nad oběma zastoupenými abecedami
• standardní operace: sjednoccení, průnik, rozdíl
• zřetězení jazyků L a K je jazyk L . K = {u.v | u ∈ L, v ∈ K}, zachovává se pořadí

  1 = {0, 1}, 2 = {a, b}
  L = {00, 01}, K = {aa, bb}
  L.K = {00aa, 00bb, 01aa, 01bb}

• (prázdná množina) . L = prázdná množina, ale pozor {(prázdné slovo)} . L = L

Iterace jazyka L je jazyk L* = ∪ Li (i = 0, nekonečno)

L = {aa, b}
L = L0 ∪ L1 ∪ L2 ...
L* = {ε, aa, b, aaaa, aab, baa, bb, aaaaaa, aaaab, ... }

Pozitivní iterace L+ = L*

Doplněk jazyka L je jazyk co-L = Σ* bez L, je pro to třeba znát abecedu

L = {a, aa}
Σ = {a} co-L = {ε, aaa, aaaa, ...}
Σ = {a, b} co-L = {ε, b, ab, ba, bb} ∪ {w ∈ {a, b}* | |w| ≥ 3}

Zrcadlový obraz

{abacca}^R = accaba

Uzavřená třída jazyků

Σ = {a}

L₁ = {ε, a, aa, aaa, aaaa...}
L₂ = {a, aa, aaa, aaaa...}
L₃ = {aa, aaa, aaaa...}
L_i = {a^j | j ≥ i}

L je uzavřená na: ∪, ∩, Lⁿ | (n > 0), ., +
L není uzavřená na: (diff), L⁰, *, L+, R

L_i ∪ L_j = L_min(i,j)
L_i ∩ L_j = L_max(i,j)
L₁ ∪ L₂ = {a}

Aplikace

N = {1, 2, 3, 4...}
Σ = {0, 1, 2, 3, ... , 9}

N = {1, 2, ... , 9} . {0, 1, 2, ... 9}*
N⁰ = N . {0}
nebo N = Σ⁺ - {0} . Σ⁺

Gramatika

• je popis jazyka pomocí pravidel, podle kterých se vytvářejí všechna sova daného jazyka
• např. →
• k zadání syntaxe vyšších programovacích jazyků používáme Backus-Naurova normální formu (BNF)
• definice: Gramatika je čtveřice (N, Σ, P, S), kde
  • N je neprázdná konečná množina neterminálů
  • Σ je konečná množina terminálů, taková, že N ∩ Σ = (null) , množinu všech symbolů definujeme jako N ∪ Σ
  • P je komečná množina pravidel, pravidlo (alfa, beta) zapisujeme jako alfa → beta (alfa přepiš na beta)
  • S je počáteční terminál

  G = ({s}, {a, b}, P, S) P = {S → a, S → baS, aS → bb} ... doplnit na prtsc ...*

přímé odvození

• doplnit def. přímého odvození

odvození v k krocích

• doplnit

Větná forma

• každý řetěz z množiny V*, který lze odvodit z počátečního neterminálu gramatika

Věta gramatiky

• každá větná forma, která obsahuje pouze terminály

Konvence zápisu

Σ - terminály: a, b, c, .... , 0, 1, ... N - neterminály, S, A, B, C, ....