1. Deterministické a nedeterministické konečné automaty a jejich vztah.
2. Regulární jazyky a jejich vlastnosti. Lemma o vkládání (Pumping lemma) a Nerodova věta.
3. Regulární výrazy a jejich vztah k regulárním jazykům.
4. Bezkontextové gramatiky. Chomského hierarchie jazyků. Bezkontextové jazyky a jejich vlastnosti. Lemma o vkládání pro bezkontextové jazyky (Pumping lemma pro bezkontextové jazyky).
5. Zásobníkové automaty (nedeterministické i deterministické ) a jejich vztah k bezkontextovým jazykům.

Deterministický konečný automat (DFA) má přechodovou funkci, která z daného stavu a vstupního symbolu určuje právě jeden další stav. Má jeden počáteční stav a množinu koncových stavů. Nedeterministický konečný automat (NFA) umožňuje více možných přechodů ze stavu pro stejný vstupní symbol nebo přechody bez vstupu (ε-přechody).

Vlastnosti: Každý vstupní symbol má přesně jeden přechod (např. a přechází z $q_0$ do $q_1$, b zůstává v $q_0$).

Vlastnosti: Některé přechody jsou vícevýběrové (např. $q_0$ na vstup 0 může jít do $q_1$ nebo $q_2$).

Vlastnosti: Přechody bez vstupu (např. $q_0$ → $q_1$ přes $\varepsilon$), které umožňují “volné” přechody.

1. Ekvivalencí schopností: Každý NFA lze konstruktivně převést na ekvivalentní DFA (pomocí podmnožinové konstrukce).
2. Podmnožinová konstrukce: Stavy nového DFA reprezentují množiny stavů původního NFA. Přechody v DFA simuluji všechny možné přechody NFA.
3. Regulární jazyky: Obě modely přijímají právě třídu regulárních jazyků. Nedeterminismus nepřidává výpočetní sílu, pouze usnadňuje popis některých automatů.

Příklad: NFA hledající podslovo “011” může mít v přechodu mezi stavy více možností, ale existuje ekvivalentní DFA s přesnými přechody.

Regulární jazyky a jejich vlastnosti. Lemma o vkládání (Pumping lemma) a Nerodova věta.

Definice:
Regulární jazyk je jazyk, který lze přijmout deterministickým (alebo nedeterministickým) konečným automatem (DFA/NFA). Třída všech regulárních jazyků značíme Reg.

Vlastnosti:
1. Uzávěrnost:
- Uzavřena na sjednocení, průnik, doplněk, rozdíl, zřetězení a Kleeneho operátor (★).
- Například, pro regulární jazyky $L_1, L_2$ je $L_1 \cup L_2$, $L_1 \cap L_2$, $L_1^{\text{C}}$ i $L_1 \circ L_2$ regulární .

1. Regulární výrazy:
   • Každý regulární jazyk lze popsat regulárním výrazem, který obsahuje operace sjednocení (+), součin (kontatenace), a Kleeneho zhvězdu (★).

Lemma o vkládání (Pumping lemma):
Pro každý regulární jazyk $L$ existuje číslo $n$, takže pro každé slovo $w \in L$ s $|w| \geq n$ lze rozdělit na $w = xwy$, kde:
- $|xw| \leq n$,
- $w \neq \varepsilon$,
- $xw^i y \in L$ pro všechna $i \geq 0$.
Lemma slouží k dokazování, že určité jazyky nejsou regulární (např. $\{a^nb^n \mid n \geq 0\}$).

Nerodova věta tvrdí, že jazyk $L$ nad abecedou $\Sigma$ je regulární právě tehdy, když existuje ekvivalence $R$ na $\Sigma^*$ splňující:
1. $L$ je sjednocení některých tříd ekvivalence $R$.
2. Pro $uRv$ a libovolné $w \in \Sigma^*$ platí $uwRvw$.
3. $R$ má konečně mnoho tříd ekvivalence .

Formální popis regulárních výrazů a jejich ekvivalence s regulárními jazyky přijímanými konečnými automaty.

Regulární výrazy jsou formální zápis popisující regulární jazyky. Skládají se z operací: - Sjednocení (R|S) - Zřetězení (R·S) - Kleeneho hvězda (R*)

Každý regulární výraz lze převést na ekvivalentní ε-NFA (nedeterministický konečný automat s ε-přechody). Základní konstrukce [1]: 1. Elementární výraz a (pro a ∈ Σ):

1. Sjednocení R|S:
   • Kombinace ε-přechody z nového počátečního stavu do počátků R a S.
2. Zřetězení R·S:
   • Přidání ε-přechodů z koncových stavů R do počátečního stavu S.
3. Kleeneho hvězda R*:
   • Přidání ε-přechodů: z nového počátečního stavu do R, z koncových stavů R zpět do jeho počátku.

Příklad převodu (0|ε)1* na ε-NFA [1]:

Vysvětlení:
- Stav q0 rozděluje výpočet na větev pro 0 (přes q1) a větev pro 1* (přes q2, q3).
- Cyklus v q3 umožňuje opakované čtení 1, ε-přechody spojují komponenty bez spotřeby vstupu [1].

Regulární jazyky jsou právě ty jazyky, které lze popsat regulárním výrazem nebo přijímat konečným automatem (DFA/NFA/ε-NFA) [1].

Formální systém pro generování jazyků pomocí pravidel přepisování proměnných, schopný popsat mnoho přirozených i programovacích jazyků.

Hierarchie klasifikuje formální jazyky podle výpočetní složitosti jejich gramatik: 1. Typ 0 (Rekurzivně spočetné jazyky): Neomezené gramatiky (Turingovy stroje) 2. Typ 1 (Kontextové jazyky): Kontextové gramatiky (lineárně omezené automaty) 3. Typ 2 (Bezkontextové jazyky): Bezkontextové gramatiky (zásobníkové automaty) 4. Typ 3 (Regulární jazyky): Regulární gramatiky (konečné automaty)

Definovány čtveřicí $G = (V, \Sigma, P, S)$: - $V$: Konečná množina neterminálů (proměnné) - $\Sigma$: Konečná množina terminálů (abeceda) - $P$: Množina pravidel tvaru $A \to \alpha$ ($A \in V$, $\alpha \in (V \cup \Sigma)^*$) - $S \in V$: Počáteční symbol

Příklad gramatiky pro jazyk $L = \{a^nb^n \mid n \geq 0\}$:
$G = (\{S\}, \{a,b\}, P, S)$ s pravidly:
1. $S \to aSb$
2. $S \to \varepsilon$

1. Uzávěrové vlastnosti:
   • Uzavřené na: Sjednocení, zřetězení, iteraci, homomorfismus
     

• Neuzavřené na: Průnik, doplněk

1. Rozhodnutelné problémy:

• Prázdnost jazyka ($L(G) \overset{?}{=} \emptyset$)
  

• Náležitost slova ($w \overset{?}{\in} L(G)$ – CYK algoritmem)

1. Paměťový mechanismus: Zásobníkové automaty

Formulace: Pro každý bezkontextový jazyk $L$ existuje konstanta $p$ tak, že každé slovo $z \in L$ délky $|z| \geq p$ lze zapsat jako $z = uvwxy$ splňující:
1. $|vwx| \leq p$
2. $|vx| \geq 1$
3. $\forall i \geq 0: uv^iwx^iy \in L$

Aplikace: Důkaz, že jazyk není bezkontextový.
Příklad: Jazyk $L = \{a^nb^nc^n \mid n \geq 0\}$ není bezkontextový:
- Zvolíme $z = a^pb^pc^p$
- Pro libovolné rozdělení $z = uvwxy$:
- Pokud $vwx$ obsahuje dva druhy symbolů, pumpováním porušíme pořadí
- Pokud obsahuje jeden symbol, pumpováním změníme počet jen u jednoho písmena

Zásobníkové automaty jsou nedeterministické nebo deterministické stroje rozpoznávající bezkontextové jazyky. Nedeterministické přijímají všechny bezkontextové jazyky, zatímco deterministické pouze jejich podmnožinu (deterministické bezkontextové jazyky).

• Nedeterministický zásobníkový automat (PDA) je sedmice ($Q, \Sigma, \Gamma, \delta, q_0, Z_0, F$), kde:
  • $Q$: konečná množina stavů
    

• $\Sigma$: vstupní abeceda
  

• $\Gamma$: zásobníková abeceda
  

• $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}_f(Q \times \Gamma^*)$: přechodová funkce
  

• $q_0$: počáteční stav
  

• $Z_0$: počáteční symbol zásobníku
  

• $F$: koncové stavy
  

Přijímání: koncovým stavem $L(A) = \{w \mid (q_0, w, Z_0) \vdash_A^* (p, \varepsilon, \gamma), p \in F\}$ nebo prázdným zásobníkem $N(A) = \{w \mid (q_0, w, Z_0) \vdash_A^* (p, \varepsilon, \varepsilon)\}$ , .

• Deterministický zásobníkový automat (DPDA) má $\delta$ částečně definovanou a pro každé $(q, a, X)$ existuje nejvýše jeden přechod. Určuje deterministické jazyky .

1. Ekvivalence PDA a bezkontextových gramatik:
   • Každý jazyk generovaný bezkontextovou gramatikou $G$ je přijímán nějakým PDA prázdným zásobníkem: $L(G) = N(A)$ , .
     

• Konstrukce PDA z gramatiky:
  • Stavy: $Q = \{q\}$
    

• $\Gamma = N \cup \Sigma$, $Z_0 = S$
  

• $\delta(q, \varepsilon, X) = \{(q, \alpha) \mid X \to \alpha \in P\}$
  

• $\delta(q, a, a) = \{(q, \varepsilon)\}$ pro $a \in \Sigma$ .

1. Omezení deterministických automatů:

• DPDA přijímají pouze bezprefixové jazyky prázdným zásobníkem: Pokud $u \in N(A)$, pak žádné $uv$ ($v \neq \varepsilon$) není přijato , .
  

• Ne všechny bezkontextové jazyky jsou deterministické (např. $L = \{a^n b^n \mid n \geq 0\} \cup \{a^n b^{2n} \mid n \geq 0\}$).

1. Nedeterministický PDA pro $L = \{a^n b^n \mid n \geq 0\}$:
   • Při čtení $a$ ukládá $A$ na zásobník.
     

• Při čtení $b$ odebírá $A$ ze zásobníku.
  

• Přijímá prázdným zásobníkem.

1. Deterministický jazyk:

• $L = \{wcw^R \mid w \in \{a,b\}^*\}$ je bezprefixový a přijímaný DPDA prázdným zásobníkem, ale není regulární .

Schéma PDA pro $\{a^n b^n\}$ (přijímá při prázdném zásobníku po návratu do $q_0$)