The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
statnice:bakalar:b4b01jag [2025/05/25 11:46] – created mistrjirkastatnice:bakalar:b4b01jag [2025/06/09 18:56] (current) – [Regulární jazyky] tehlajak
Line 7: Line 7:
  
 ===== Deterministické a nedeterministické konečné automaty ===== ===== Deterministické a nedeterministické konečné automaty =====
-**Deterministické a nedeterministické konečné automaty a jejich vztah.**+ 
 +**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//). 
 + 
 +==== Vizualizace ==== 
 + 
 +=== Deterministický automat (DFA) === 
 + 
 +<tikzjax> 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\usepackage{amsmath} 
 +\begin{document} 
 + 
 +\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto] 
 +    \node[state, initial] (q0) {$q_0$}; 
 +    \node[state, accepting, right of=q0] (q1) {$q_1$}; 
 +    \path[->] 
 +    (q0) edge node {a} (q1) 
 +    (q0) edge [loop above] node {b} (); 
 +\end{tikzpicture} 
 + 
 +\end{document} 
 +</tikzjax> 
 +**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$). 
 + 
 +=== Nedeterministický automat (NFA) === 
 + 
 +<tikzjax> 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\usepackage{amsmath} 
 +\begin{document} 
 + 
 +\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto] 
 +    \node[state, initial] (q0) {$q_0$}; 
 +    \node[state, right of=q0] (q1) {$q_1$}; 
 +    \node[state, accepting, below of=q1] (q2) {$q_2$}; 
 +    \path[->] 
 +    (q0) edge node {0} (q1) 
 +    (q0) edge node {0} (q2) 
 +    (q1) edge node {1} (q2); 
 +\end{tikzpicture} 
 + 
 +\end{document} 
 +</tikzjax> 
 +**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$). 
 + 
 +=== Epsilon-NFA (s ε-přechody) === 
 + 
 +<tikzjax> 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\usepackage{amsmath} 
 +\begin{document} 
 + 
 +\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto] 
 +    \node[state, initial] (q0) {$q_0$}; 
 +    \node[state, right of=q0] (q1) {$q_1$}; 
 +    \node[state, accepting, below of=q1] (q2) {$q_2$}; 
 +    \path[->] 
 +    (q0) edge [above] node {$\varepsilon$} (q1) 
 +    (q1) edge [below] node {a} (q2); 
 +\end{tikzpicture} 
 + 
 +\end{document} 
 +</tikzjax> 
 +**Vlastnosti**: Přechody bez vstupu (např. $q_0$ → $q_1$ přes $\varepsilon$), které umožňují “volné” přechody. 
 + 
 + 
 +---- 
 + 
 +==== Vztah mezi DFA a NFA: ==== 
 + 
 +  - **Ekvivalencí schopností**: Každý NFA lze konstruktivně převést na ekvivalentní DFA (pomocí //podmnožinové konstrukce//). 
 +  - **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. 
 +  - **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 ===== ===== Regulární jazyky =====
 +
 **Regulární jazyky a jejich vlastnosti. Lemma o vkládání (Pumping lemma) a Nerodova věta.** **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í .
 +
 +  - **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 $u \in L$ s $|u| > n$ lze rozdělit na $u = 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 .
  
 ===== Regulární výrazy ===== ===== Regulární výrazy =====
-**Regulární výrazy a jejich vztah k regulárním jazykům.**+ 
 +**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 ∈ Σ%%''): 
 + 
 +<tikzjax> 
 +\usepackage{amsmath} 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[shorten >=1pt, node distance=2cm, auto] 
 +\node[state, initial] (q0) {}; 
 +\node[state, accepting] (q1) [right of=q0] {}; 
 +\path[->] (q0) edge node {a} (q1); 
 +\end{tikzpicture} 
 +\end{document} 
 +</tikzjax> 
 +  - **Sjednocení ''%%R|S%%''**: 
 +    * Kombinace ε-přechody z nového počátečního stavu do počátků R a S. 
 +  - **Zřetězení ''%%R·S%%''**: 
 +    * Přidání ε-přechodů z koncových stavů R do počátečního stavu S. 
 +  - **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]: 
 + 
 +<tikzjax> 
 +\usepackage{amsmath} 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[shorten >=1pt, node distance=2cm, auto] 
 +\node[state, initial] (q0) {$q_0$}; 
 +\node[state] (q1) [above right of=q0] {$q_1$}; 
 +\node[state] (q2) [below right of=q0] {$q_2$}; 
 +\node[state] (q3) [right of=q2] {$q_3$}; 
 +\node[state, accepting] (q4) [right of=q3] {$q_4$}; 
 +\path[->]  
 +(q0) edge node {$\varepsilon$} (q1) 
 +      edge node {$\varepsilon$} (q2) 
 +(q1) edge node {0} (q4) 
 +(q2) edge node {$\varepsilon$} (q3) 
 +(q3) edge [loop above] node {1} () 
 +      edge node {$\varepsilon$} (q4); 
 +\end{tikzpicture} 
 +\end{document} 
 +</tikzjax> 
 +//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].
  
 ===== Bezkontextové gramatiky ===== ===== Bezkontextové gramatiky =====
-**Bezkontextové gramatiky. Chomského hierarchie jazyků. Bezkontextové jazyky a jejich vlastnosti. Lemma o vkládání pro bezkontextové jazyky (Pumping lemma pro bezkontextové jazyky).** 
  
 +**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ů.**
 +
 +==== Chomského hierarchie 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)
 +
 +=== Bezkontextové gramatiky ===
 +
 +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$
 +
 +=== Vlastnosti bezkontextových jazyků ===
 +
 +  - **Uzávěrové vlastnosti**:
 +    * Uzavřené na: Sjednocení, zřetězení, iteraci, homomorfismus\\
 +
 +    * Neuzavřené na: Průnik, doplněk
 +  - **Rozhodnutelné problémy**:
 +    * Prázdnost jazyka ($L(G) \overset{?}{=} \emptyset$)\\
 +
 +    * Náležitost slova ($w \overset{?}{\in} L(G)$ – CYK algoritmem)
 +  - **Paměťový mechanismus**: Zásobníkové automaty
 +
 +=== Lemma o vkládání (Pumping Lemma) ===
 +
 +**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 ===== ===== Zásobníkové automaty =====
-**Zásobníkové automaty (nedeterministické i deterministické ) a jejich vztah k bezkontextovým jazykům.**+ 
 +**Zásobníkové automaty (nedeterministické i deterministické) a jejich vztah k bezkontextovým jazykům.** 
 + 
 +==== Definice ==== 
 + 
 +Zásobníkový automat (PDA) je sedmice $A = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, kde: - $Q$: konečná množina stavů. - $\Sigma$: vstupní abeceda. - $\Gamma$: zásobníkové symboly. - $\delta$: přechodová funkce $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$. - $q_0$: počáteční stav. - $Z_0$: počáteční zásobníkový symbol. - $F \subseteq Q$: koncové stavy. 
 + 
 +==== Typy zásobníkových automatů ==== 
 + 
 +  - <WRAP> 
 +**Nedeterministický PDA (NPDA):** 
 +    * Přechody mohou být více možností. 
 +    * Přijímá jazyk $L(A) = \{ w \mid (q_0, w, Z_0) \vdash_A^* (p, \varepsilon, \gamma), p \in F \}$. 
 +    * **Příklad:** Jazyk $L = \{ a^n b^n \mid n \geq 0 \}$. 
 +<tikzjax> 
 +\usepackage{amsmath} 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\begin{document} 
 + 
 +\begin{tikzpicture}[node distance=2cm] 
 +\node[state, initial] (q0) {$q_0$}; 
 +\path[->] 
 +(q0) edge [loop above] node {\(a, Z_0 \to AZ_0\)} (q0) 
 +(q0) edge [loop below] node {\(b, A \to \varepsilon\)} (q0); 
 +\end{tikzpicture} 
 + 
 +\end{document} 
 +</tikzjax> 
 +    * Na $a$ zásobník naplní symboly $A$. 
 +    * Na $b$ zásobník vyprázdní $A$. 
 +</WRAP> 
 +  - <WRAP> 
 +**Deterministický PDA (DPDA):** 
 +    * Pro každý stav $q$, symbol $a \in \Sigma \cup \{\varepsilon\}$ a vrchol $X \in \Gamma$ je $|\delta(q,a,X)| \leq 1$. 
 +    * Pokud $\delta(q,\varepsilon,X) \neq \emptyset$, pak $\delta(q,a,X) = \emptyset$ pro všechna $a \in \Sigma$. 
 +    * **Příklad:** Jazyk $L = \{ a^n b^n c^n \mid n \geq 0 \}$ nelze přijmout deterministicky, ale např. jazyk $L = \{ a^n b^n \mid n \geq 0 \}$ s přísnými přechody: 
 +<tikzjax> 
 +\usepackage{amsmath} 
 +\usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} 
 +\begin{document} 
 + 
 +\begin{tikzpicture}[node distance=2cm] 
 +\node[state, initial] (q0) {$q_0$}; 
 +\node[state, right of=q0] (q1) {$q_1$}; 
 +\path[->] 
 +(q0) edge [loop above] node {\(a, Z_0 \to AZ_0\)} (q0) 
 +(q0) edge node {\(b, A \to \varepsilon\)} (q1) 
 +(q1) edge [loop below] node {\(b, A \to \varepsilon\)} (q1); 
 +\end{tikzpicture} 
 + 
 +\end{document} 
 +</tikzjax> 
 +    * Determinismus vyžaduje, aby přechody na $a$ a $b$ byly navzájem vyloučené. 
 +</WRAP> 
 + 
 +==== Vztah k bezkontextovým jazykům ==== 
 + 
 +  * **Věta 0.4.9:** Každá bezkontextová gramatika $G$ lze převést na NPDA $A$, takže $L(G) = N(A)$. 
 +  * **Podstatné rozdíly:** 
 +    * NPDA přijímají všechny bezkontextové jazyky. 
 +    * DPDA přijímají podmnožinu (deterministické jazyky). Například jazyk $\{ a^n b^n c^n \}$ není deterministický. 
 + 
 +==== Bezprefixové jazyky ==== 
 + 
 +  * Jazyk přijatý DPDA prázdným zásobníkem je **bezprefixový** (neobsahuje slovo jako prefix jiného slova). 
 +  * Pro každý DPDA $A$ existuje DPDA $B$, který přijímá $N(A) = L(B)$ koncovým stavem [1]. 
 + 

Trace: • b4b33alg • b0b36dbs

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b01jag (generated for current page)