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:

Navigation

Playground

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