Differences

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

--- statnice:bakalar:b4b01jag [2025/06/06 21:57] – [Regulární výrazy] mistrjirka
+++ statnice:bakalar:b4b01jag [2025/06/09 18:56] (current) – [Regulární jazyky] tehlajak
@@ Line 99: / Line 99: @@
 **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:\\
+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$,\\
@@ Line 165: / Line 165: @@
 ===== 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:\\
+. $S \to aSb$\\
+. $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í:\\
+. $|vwx| \leq p$\\
+. $|vx| \geq 1$\\
+. $\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 (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:

Differences

Search

Navigation

Print/export

Tools

QR Code