Differences

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

--- statnice:bakalar:b4b01jag [2025/06/06 22:05] – [Bezkontextové gramatiky] 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 206: / Line 206: @@
 - 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: • b6b36ts1 • b4b39hry • b4b36pdv • b4b36fup

Differences

Search

Navigation

Print/export

Tools

QR Code