Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b01jag [2025/06/07 10:04] – [Zásobníkové automaty] mistrjirkastatnice:bakalar:b4b01jag [2025/06/09 18:56] (current) – [Regulární jazyky] tehlajak
Line 99: Line 99:
  
 **Lemma o vkládání (Pumping lemma):**\\ **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$,\\ - $|xw| \leq n$,\\
 - $w \neq \varepsilon$,\\ - $w \neq \varepsilon$,\\
Line 206: Line 206:
 - Pokud $vwx$ obsahuje dva druhy symbolů, pumpováním porušíme pořadí\\ - 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 - 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 jsou nedeterministické nebo deterministické stroje rozpoznávající bezkontextové jazyky. Nedeterministické přijímají všechny bezkontextové jazyky, zatímco deterministické pouze jejich podmnožinu (deterministické bezkontextové jazyky).**+==== Definice ====
  
-===== 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.
  
-  * **Nedeterministický zásobníkový automat (PDA)** je sedmice ($Q, \Sigma, \Gamma, \delta, q_0, Z_0, F$), kde: +==== Typy zásobníkových automatů ====
-    * $Q$: konečná množina stavů\\+
  
-    * $\Sigma$: vstupní abeceda\\+  - <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}
  
-    * $\Gamma$: zásobníková abeceda\\ +\begin{tikzpicture}[node distance=2cm] 
- +\node[state, initial] (q0) {$q_0$}; 
-    * $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}_f(Q \times \Gamma^*)$: přechodová funkce\\ +\path[->] 
- +(q0) edge [loop above] node {\(a, Z_0 \to AZ_0\)} (q0) 
-    * $q_0$: počáteční stav\\ +(q0) edge [loop below] node {\(b, A \to \varepsilon\)} (q0); 
- +\end{tikzpicture}
-    * $Z_0$: počáteční symbol zásobníku\\ +
- +
-    * $F$: koncové stavy\\ +
-Přijímání: **koncovým stavem** $L(A) = \{w \mid (q_0, w, Z_0) \vdash_A^* (p, \varepsilon, \gamma), p \in F\}$ nebo **prázdným zásobníkem** $N(A) = \{w \mid (q_0, w, Z_0) \vdash_A^* (p, \varepsilon, \varepsilon)\}$ , . +
-  * **Deterministický zásobníkový automat (DPDA)** má $\delta$ částečně definovanou a pro každé $(q, a, X)$ existuje nejvýše jeden přechod. Určuje **deterministické jazyky** . +
- +
-===== Vztah k bezkontextovým jazykům ===== +
- +
-  - **Ekvivalence PDA a bezkontextových gramatik**: +
-    * Každý jazyk generovaný bezkontextovou gramatikou $G$ je přijímán nějakým PDA prázdným zásobníkem: $L(G) = N(A)$ , .\\ +
- +
-    * Konstrukce PDA z gramatiky: +
-      * Stavy: $Q = \{q\}$\\ +
- +
-      * $\Gamma = N \cup \Sigma$, $Z_0 = S$\\ +
- +
-      * $\delta(q, \varepsilon, X) = \{(q, \alpha) \mid X \to \alpha \in P\}$\\ +
- +
-      * $\delta(q, a, a) = \{(q, \varepsilon)\}$ pro $a \in \Sigma$ . +
-  - **Omezení deterministických automatů**: +
-    * DPDA přijímají pouze **bezprefixové jazyky** prázdným zásobníkem: Pokud $u \in N(A)$, pak žádné $uv$ ($v \neq \varepsilon$) není přijato , .\\ +
- +
-    * Ne všechny bezkontextové jazyky jsou deterministické (např. $L = \{a^n b^n \mid n \geq 0\} \cup \{a^n b^{2n} \mid n \geq 0\}$). +
- +
-===== Příklady ===== +
- +
-  - **Nedeterministický PDA pro $L = \{a^n b^n \mid n \geq 0\}$**: +
-    * Při čtení $a$ ukládá $A$ na zásobník.\\ +
- +
-    * Při čtení $b$ odebírá $A$ ze zásobníku.\\ +
- +
-    * Přijímá prázdným zásobníkem. +
-  - **Deterministický jazyk**: +
-    * $L = \{wcw^R \mid w \in \{a,b\}^*\}$ je bezprefixový a přijímaný DPDA prázdným zásobníkem, ale není regulární .+
  
 +\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> <tikzjax>
 \usepackage{amsmath} \usepackage{amsmath}
Line 264: Line 248:
 \begin{document} \begin{document}
  
-\beign{document} +\begin{tikzpicture}[node distance=2cm] 
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick] +\node[state, initial] (q0) {$q_0$}; 
-\node[state,initial] (q0) {$q_0$}; +\node[state, right of=q0] (q1) {$q_1$}; 
-\node[state,accepting] (q1) [right of=q0] {$q_1$}; +\path[->] 
-\path (q0) edge [loop above] node {  +(q0) edge [loop above] node {\(a, Z_0 \to AZ_0\)} (q0) 
-    $a, \varepsilon/A$ \\ +(q0) edge node {\(b, A \to \varepsilon\)} (q1) 
-    $b, A/\varepsilon$  +(q1) edge [loop below] node {\(b, A \to \varepsilon\)} (q1);
-} (q0);+
 \end{tikzpicture} \end{tikzpicture}
-\end{document} 
  
 \end{document} \end{document}
 </tikzjax> </tikzjax>
-//Schéma PDA pro $\{a^n b^n\}$ (přijímá při prázdném zásobníku po návratu do $q_0$)//+    * 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)