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

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b01jag [2025/06/07 10:07] – [Příklady] 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}
 \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta}
 \begin{document} \begin{document}
  
-\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick] +\begin{tikzpicture}[node distance=2cm] 
-\node[state,initial] (q0) {$q_0$}; +\node[state, initial] (q0) {$q_0$}; 
-\node[state,accepting] (q1) [right of=q0] {$q_1$}; +\node[state, right of=q0] (q1) {$q_1$}; 
-\path (q0) edge [loop above] node {  +\path[->] 
-    $a, \varepsilon/A$ \\ +(q0) edge [loop above] node {\(a, Z_0 \to AZ_0\)} (q0) 
-    $b, A/\varepsilon$  +(q0) edge node {\(b, A \to \varepsilon\)} (q1) 
-} (q0);+(q1) edge [loop below] node {\(b, A \to \varepsilon\)} (q1);
 \end{tikzpicture} \end{tikzpicture}
  
 \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)