Regulární jazyky a bezkontextové jazyky. Popis těchto jazyků pomocí automatů a gramatik, vlastnosti regulárních a bezkontextových jazyků

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) [2]. 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 (★) [3].
- 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í [3].

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 (★) [3].

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$ [3].
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 .

Regulární výrazy a jejich vztah k regulárním jazykům.

Bezkontextové gramatiky. Chomského hierarchie jazyků. Bezkontextové jazyky a jejich vlastnosti. Lemma o vkládání pro bezkontextové jazyky (Pumping lemma pro bezkontextové jazyky).

Zásobníkové automaty (nedeterministické i deterministické ) a jejich vztah k bezkontextovým jazykům.