====== AP11, IN11 Zásobníkové automaty, Syntaktická analýza ======

===== Zadání =====
(definice, převod bezkontextové gramatiky na zásobníkový automat)

(syntaktická analýza shora dolů a zdola nahoru, průběh analýzy daného slova)

===== Vypracování =====

==== Intuice zásobníkového automatu ====
Zásobníkový automat = PushDown Automaton = PDA

Na vstupní pásce je napsáno slovo (nad jistou vstupní abecedou) -- lze z ní pouze číst, čtecí hlava se pohybuje pouze vpravo. Automat může na vrchol zásobníku ukládat symboly (z jisté abecedy) a ty následně číst -- čte vždy jen vrchol zásobníku, přečtený symbol je odstraněn = systém LIFO (Last In First Out).

==== Formální definice ====
<box 95% round blue|Definice 3.36. - PDA ((skripta Automaty a formální jazyky I, str. 77))>**Nedeterministický zásobníkový automat** (PushDown Automaton, PDA) je sedmice  <math>M = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F)</math>, kde
• Q je konečná množina, jejíž prvky nazýváme stavy,
• <math>\Sigma</math> je konečná množina, tzv. vstupní abeceda,
• <math>\Gamma</math> je konečná množina, tzv. zásobníková abeceda,
• <math>\delta : (Q \times (\Sigma \cup{{\varepsilon}})\times \Gamma) \rightarrow P_{Fin}(Q \times \Gamma^{*})</math>, tzv. (parciální) přechodová funkce (zápis <math>P_{Fin}(Q \times \Gamma^{*})</math> značí množinu všech konečných podmnožin množiny <math>Q\times \Gamma^{*}</math> -- dvojice stav a řetězec symbolů zásobníkové abecedy),
• <math>q_{0} \in Q</math> je počáteční stav,
• <math>Z_{0} \in \Gamma</math> je počáteční symbol v zásobníku,
• <math>F \subseteq Q</math> je množina koncových stavů.
</box>

<math>\delta(q_{0}, a, Z_{0}) = \{(q_{0}, AZ_{0})\}; Z_{0}</math> ... dno zásobníku, A ... vrchol zásobníku, přidal se v tomto kroku
<math>\delta(q_{0}, c,  A) = \{(q_{1}, A)\}</math> ... obsah zásobníku se nezměnil, pouze se přešlo do stavu q<sub>1</sub>
<math>\delta(q_{1}, b, A) = \{(q_{1}, \varepsilon)\}</math> ... stav se nezměnil, ze zásobníku se přečetlo A -- bylo odebráno
**<color blue>vrchol zásobníku běžného PDA se píše vlevo</color>**

==== Výpočet zásobníkového automatu ====

<box 95% round blue|Definice 3.37. Konfigurace, krok výpočtu ((skripta Automaty a formální jazyky I, str. 78))>Nechť <math>M = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F)</math> je PDA.
**Konfigurací** nazveme libovolný prvek <math>(p, w, \alpha) \in Q \times \Sigma^{*} \times \Gamma^{*}</math>.
Na množině všech konfigurací automatu M definujeme binární relaci **krok výpočtu** <math>|\frac{\ \ \ }{\ M \ }</math> takto:
<math>(p, aw, Z \alpha) |\frac{\ \ \ }{\ M \ }(q, w, \gamma \alpha) \Leftrightarrow^{def} \exists(q, \gamma) \in  \delta (p, a, Z)</math> pro <math>a \in \Sigma \cup \lbrace \varepsilon \rbrace</math>

Reflexivní a tranzitivní uzávěr relace <math>|\frac{\ \ \ }{\ M \ }</math> značíme <math>|\frac{\ * \ }{\ M \ }</math>.
Je-li M zřejmý z kontextu, píšeme pouze <math>|\frac{\ \ \ }{\ \ \ }</math> resp. <math>|\frac{\ * \ }{\ \ \ }</math>.</box>

=== Akceptující výpočet PDA ===

<box 95% round blue|Definice 3.37. (pokračování) -  akceptování ((skripta Automaty a formální jazyky I, str. 78))>**Jazyk akceptovaný** PDA M **koncovým stavem** definujeme jako
<math>L(M) = \lbrace w \in \Sigma^{*} | (q_{0}, w, Z_{0}) |\frac{\ * \ }{\ \ \ } (q_{f}, \varepsilon, \alpha)</math>, kde <math>q_{f} \in  F, \alpha \in \Gamma^{*} \rbrace</math>

a jazyk akceptovaný PDA M **prázdným zásobníkem** definujeme
<math>L_{e}(M) = \lbrace w \in \Sigma^{*} | (q_{0}, w, Z_{0}) |\frac{\ * \ }{\ \ \ } (q, \varepsilon, \varepsilon)</math>, kde <math>q \in Q \rbrace</math>.</box>

Takto definovaný PDA je nedeterministický -- akceptuje slovo, jestliže existuje **alespoň jeden výpočet**, který vede z počáteční konfigurace do akceptující. V případě možnosti automat "hádá správně".

==== Grafická reprezentace konfigurací ===

  * Zpravidla nekonečné
  * **Vnitřní konfigurace** (= částečná konfigurace) = aktuální stav a celý obsah zásobníku (vrchol se píše vlevo)

**Příklad:**
PDA <math> A = (\{q, r\}, \{a, b, c\}, \{Z, A\}, \delta, q, Z, \{r\})</math> - akceptuje koncovým stavem
PDA <math>A'= (\{q, r\}, \{a, b, c\}, \{Z, A\}, \delta, q, Z, \emptyset)</math> - akceptuje prázdným zásobníkem

Přechodovou funkci mají oba automaty stejnou:
<math>\delta(q, a, Z) = \{(q, AZ)\}</math>
<math>\delta(q, a, A) = \{(q, AA)\}</math>
<math>\delta(q, c, Z) = \{(r, Z)\}</math>
<math>\delta(q, c, A) = \{(r, A)\}</math>
<math>\delta(r, b, Z) = \{(r, \epsilon)\}</math>
<math>\delta(r, b, A) = \{(r, \epsilon)\} </math>

Grafické znázornění obou automatů, žlutě vybarvené jsou konfigurace, ve kterých akceptuje automat A, v tlustě orámované konfiguraci akceptuje automat A'
{{:home:inf:pda_graficky.png|}}

==== Ekvivalence dvou způsobů akceptování ====

Pro každý jazyk L platí:
<box 95%  round green| Věta 3.39, ((skripta Automaty a formální jazyky I, str. 78))><math>L = L(N)</math> pro nějaký PDA N <math>\Leftrightarrow  L = L_{e}(M)</math> pro nějaký PDA M.</box>
PDA **N** akceptuje koncovým stavem, PDA **M** prázdným zásobníkem
=== koncový stav => prázdná paměť ===
**Intuice:**
K danému N zkonstruujeme M simulující jeho činnost.
Vejde-li N do koncového stavu, M se nedeterministicky rozhodne
• pokračovat v simulaci automatu N nebo
• přejít do nově přidaného stavu <math>q_{\varepsilon}</math>, v němž vyprázdní zásobník.
**Komplikace:**
Automat N by vyprázdnil zásobník, aniž by došel do koncového stavu -- akceptoval by i nežádoucí vstup.
**Řešení:**
Před zahájením simulace bude u M na dně zásovníku nový symbol, který nedovolíme odstranit jinde, než ve stavu <math>q_{\varepsilon}</math>.

=== prázdná paměť => koncový stav ===
K danému M zkonstruujeme N simulující jeho činnost.
• N si před simulací přidá na dno zásobníku nový symbol.
• Je-li N schopen číst tento symbol (tj. zásobník automatu M je prázdný), potom N přejde do nově přidaného stavu <math>q_{f}</math>, který je koncovým stavem.

důkaz viz skripta (( skripta Automaty a formální jazyky I, str. 78)), konstrukce viz slidy (([[http://www.fi.muni.cz/~xstrejc/IB102/|Web IB102]] - slajdy10, str. 5 a 8))

==== Rozšířený zásobníkový automat ====
<box 95% round blue|Definice 3.44., Rozšířený PDA ((skripta Formální jazyky a automaty I, str. 82))>- sedmice <math>R = (Q, \Sigma, \Gamma, \delta, q_{0}, Z_{0}, F)</math>, kde 
• všechny symboly až na <math>\delta</math> mají stejný význam jako v definici PDA,
• <math>\delta</math> je zobrazením
**z konečné podmnožiny** množiny <math>Q \times (\Sigma \cup \lbrace \varepsilon \rbrace)\times\Gamma^{*}</math>,
**do konečných podmnožin** množiny <math>Q \times \Gamma^{*}</math>.</box>
Pojmy konfigurace a akceptovaný jazyk (koncovým stavem, prázdným zásobníkem) zůstávají beze změny. Krok výpočtu <math>|\frac{\ \ \ }{\ R \ }</math> definujeme takto:
<math>(p, aw, \gamma_{1} \alpha) |\frac{\ \ \ }{\ R \ } (q, w,  \gamma_{2} \alpha) \Leftrightarrow^{def} \exists(q, \gamma_{2}) \in \delta (p, a, \gamma_{1})</math> pro <math>a \in \Sigma \cup \lbrace \varepsilon \rbrace</math>

=== Ekvivalence rozšířených PDA a PDA ===
<box 95% round green|Lemma 3.45. ((skripta Formální jazyky a automaty I, str. 82))>Ke každému rozšířenému PDA existuje ekvivalentní (obyčejný) PDA.</box><color green>(Důkaz: skripta Formální jazyky a automaty I, str. 82)</color>

==== Zásobníkové automaty a bezkontextové jazyky ====
{{:home:inf:pda.png}}
**Problém syntaktické analýzy pro bezkontextové gramatiky:** pro danou bezkontextovou gramatiku G a slovo w rozhodnout, zda <math>w \in L(G)</math>.

=== Ekvivalence bezkontextových gramatik a zásobníkových automatů ===
<box 95% round green|Věta 3.51 ((skripta Formální jazyky a automaty I, str. 86))>Ke každému PDA M lze sestrojit CFG G takovou, že <math>L_{e}(M) = L(G)</math>.</box><box 95% round green|Věta 3.47 ((skripta Formální jazyky a automaty I, str. 83))>Ke každé CFG G lze sestrojit PDA M takový, že <math>L(G) = L_{e}(M)</math>.</box><box 95% round green|Důsledek 3.52 ((skripta Formální jazyky a automaty I, str. 89))>Třída jazyků rozpoznávaných zásobníkovými automaty je právě třída bezkontextových jazyků.</box>Konstrukce PDA řeší problém syntaktické analýzy. (platí pro dané G a w: <math>w \in L(G)?</math>)
<math>w \in L(G) \Leftrightarrow</math> v G existuje derivační strom s výsledkem w.

== Nedeterministická syntaktická analýza shora dolů ==
Budování derivačního stromu simuluje levé derivace, tj. vždy rozvíjíme nejlevější neterminál.<box 95% round green|Důsledek 3.47 ((skripta Formální jazyky a automaty I, str. 83))>Ke každé CFG G lze sestrojit PDA M takový, že <math>L(G) = L_{e}(M)</math>.</box>**Důkaz.** K dané gramatice G konstruujeme PDA M, který simuluje levé derivace v G (rozvíjíme nejlevější neterminál).
  * V levé derivaci je v jednom kroku odvození nahrazen (nejlevější) neterminál A pravou stranou <math>X_{1} ...X_{n}</math> nějakého A-pravidla.
  * V M této situaci odpovídá náhrada A na vrcholu zásobníku řetězem <math>X_{1} ...X_{n}</math>.
<math>M = (\lbrace q \rbrace, \Sigma,N \cup \Sigma, \delta, q, S, \emptyset)</math>, kde <math>\delta</math> je definována:
  * <math>\delta(q, \varepsilon, A)</math> obsahuje <math>(q, \alpha)</math> právě když <math>A \rightarrow \alpha \in P</math>
  * <math>\delta(q, a, a) = \lbrace(q, \varepsilon)\rbrace</math> pro všechna <math>a \in \Sigma</math>

korektnost + důkaz viz skripta ((str. 84 skripta Formální jazyky a automaty I, slajdy11 - str. 12))

== Nedeterministická syntaktická analýza zdola nahoru ==
<box 95% round green|Lemma 3.55 ((skripta Formální jazyky a automaty I, str. 90))>Nechť G je libovolná CFG, pak lze zkonstruovat rozšířený PDA R takový, že L(G) = L(R).</box>**Důkaz.** 
**<color blue>Vrchol zásobníku píšeme vpravo.</color>**
Konstruujeme rozšířený PDA R, který simuluje pravou derivaci v G v obráceném pořadí.
PDA R má kroky dvojího typu:
  - může kdykoli číst do zásobníku vstupní symbol,
  - **(redukce)** je-li na vrcholu zásobníku řetěz tvořící pravou stranu nějakého pravidla v G, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte).

Nechť <math>G = (N, \Sigma, P, S)</math>.
Položme <math>R = (\lbrace q, r \rbrace, \Sigma, N \cup \Sigma \cup \lbrace \bot \rbrace, \delta, q, \bot, \lbrace r \rbrace )</math>, kde <math>\bot</math> je nově přidaný symbol a kde <math>\delta</math> je definována takto:
  - <math>\delta(q, a, \varepsilon) = \lbrace(q, a)\rbrace</math> pro všechna <math>a \in \Sigma</math> //...načítání vstupu na zásobník//,
  - je-li <math>A \rightarrow \alpha</math>, pak <math>\delta(q, \varepsilon, \alpha)</math> obsahuje (q, A) //...redukce//,
  - <math>\delta(q, \varepsilon, \bot S) = \lbrace(r, \varepsilon)\rbrace</math> //...akceptování//.
korektnost viz slajdy ((slajdy11, str. 17))

== Příklad: ==
Zadání: 
G = ({S, A, B}, {a, b}, P, S)
P = 
{S -> <math>\varepsilon</math> | abSA
 A -> AaB | aB | a,
 B -> aSS | bA | <math>\varepsilon</math>}
Derivační strom pro slovo w = abababaa
{{:home:inf:pda_analyza.png}}
**Automat, který provádí syntaktickou analýzu shora dolů:**
A = ({q}, {a,b}, {S, A, B, a, b}, <math>\delta</math>, q, S, <math>\emptyset</math>)
2 typy přechodových fcí:
  * //levou stranu pravidel z gram. dáváme na zásobník levé strany přechodové fce PDA,    pravou stranu pravidel z gram. na zásobník pravé strany//
<math>\delta</math>(q, <math>\varepsilon</math>, S) = {(q, <math>\varepsilon</math>), (q, abSA)}
<math>\delta</math>(q, <math>\varepsilon</math>, A) = {(q, AaB), (q, aB), (q, a)}
<math>\delta</math>(q, <math>\varepsilon</math>, B) = { (q, aSS), (q, bA), (q, <math>\varepsilon</math>)}
  * //"mazací" přechodové fce//
<math>\delta</math>(q, a, a) = {(q, <math>\varepsilon</math>)}
<math>\delta</math>(q, b, b) = {(q, <math>\varepsilon</math>)}

  * **Akceptující výpočet nad slovem abababaa:**
(intuice: postupuju podle derivačního stromu, sleduju jeho rozvíjení odshora a čtu ho zleva)
**<color red>vrchol zásobníku je vlevo</color>**
<math>(q, abababaa, S) |\frac{\ \ \ }{\ \ \ } (q, abababaa, abSA) |\frac{\ \ \ }{\ \ \ } (q, bababaa, bSA) |\frac{\ \ \ }{\ \ \ } </math>\\
 <math>(q, ababaa, SA) |\frac{\ \ \ }{\ \ \ } (q, ababaa, A) |\frac{\ \ \ }{\ \ \ } (q, ababaa, AaB) |\frac{\ \ \ }{\ \ \ } </math>\\
 <math> (q, ababaa, aBaB) |\frac{\ \ \ }{\ \ \ } (q, babaa, BaB) |\frac{\ \ \ }{\ \ \ } (q, babaa, bAaB) |\frac{\ \ \ }{\ \ \ } </math>\\
 <math> (q, abaa, AaB) |\frac{\ \ \ }{\ \ \ } (q, abaa, aBaB) |\frac{\ \ \ }{\ \ \ } (q, baa, BaB) |\frac{\ \ \ }{\ \ \ }</math>\\ 
 <math> (q, baa, bAaB) |\frac{\ \ \ }{\ \ \ } (q, aa, AaB) |\frac{\ \ \ }{\ \ \ } (q, aa, aaB) |\frac{\ \ \ }{\ \ \ } </math>\\ 
 <math>(q, a, aB) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, B) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \varepsilon)</math>
... celé slovo se přečetlo a zásobník se vyprázdnil <math>\rightarrow</math> **automat slovo akceptuje**

**Automat pro syntaktickou analýzu zdola nahoru:**
<math>A_{2} = (\{q, r\}, \{ a,b\} , \{S, A, B, a, b, \bot\}, \delta, q, \bot, \{ r\})</math>
3 typy přechodových funkcí:
  * //terminály z gramatiky se předávají na zásobník//
<math>\delta</math>(q, a, <math>\varepsilon</math>) = {(q, a)}
<math>\delta</math>(q, b, <math>\varepsilon</math>) = {(q, b)}
  * //pravou stranu pravidel z gram. dáváme na zásobník levé strany přechodové fce PDA,    levou stranu pravidel z gram. na zásobník pravé strany//
<math>\delta</math>(q, <math>\varepsilon</math>, abSA) = {(q, S)}
<math>\delta</math>(q, <math>\varepsilon</math>, <math>\varepsilon</math>) = {(q, S), (q, B)} **<color red>! ! !</color>** Nesmí být rozděleno na: <math>\delta</math>(q, <math>\varepsilon</math>, <math>\varepsilon</math>) = {(q, S)} a <math>\delta</math>(q, <math>\varepsilon</math>, <math>\varepsilon</math>) = {(q, B)}, nebyla by to pak funkce.
<math>\delta</math>(q, <math>\varepsilon</math>, AaB) = <math>\delta</math>(q, <math>\varepsilon</math>, aB) = <math>\delta</math>(q, <math>\varepsilon</math>, a) = {(q, A)}
<math>\delta</math>(q, <math>\varepsilon</math>, aSS) = <math>\delta</math>(q, <math>\varepsilon</math>, bA) = {(q, B)}
  * //přechod do koncového stavu//
<math>\delta</math>(q, <math>\varepsilon</math>,  <math>\bot</math>S) = {(r, <math>\varepsilon</math>)}


  * **Akceptující výpočet nad slovem abababaa:**
(Intuice: čtu derivační strom zleva -- jako když teče voda (= používám první skupinu pravidel), pokud by voda musela téct do kopce, použiju pravidlo z druhé skupiny)
**<color red>vrchol zásobníku je vpravo</color>**
<math>(q, abababaa, \bot) |\frac{\ \ \ }{\ \ \ } (q, bababaa, \bot a) |\frac{\ \ \ }{\ \ \ } (q, ababaa, \bot ab) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, ababaa, \bot abS) |\frac{\ \ \ }{\ \ \ } (q, babaa, \bot abSa) |\frac{\ \ \ }{\ \ \ } (q, abaa, \bot abSab) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, baa, \bot abSaba) |\frac{\ \ \ }{\ \ \ } (q, aa, \bot abSabab) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSababa) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, a, \bot abSababA) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSabaB) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSabA) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, a, \bot abSaB) |\frac{\ \ \ }{\ \ \ } (q, a, \bot abSA) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot abSAa) |\frac{\ \ \ }{\ \ \ }</math>\\
 <math> (q, \varepsilon, \bot abSAaB) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot abSA) |\frac{\ \ \ }{\ \ \ } (q, \varepsilon, \bot S) |\frac{\ \ \ }{\ \ \ } (r, \varepsilon, \varepsilon)</math>
... automat přečetl celé slovo a přešel do koncového stavu r, **slovo akceptuje**.

U nedeterministické analýzy automat slovo neakceptuje, pokud **žádný** z možných výpočtů není akceptující.
=== Efektivnost syntaktické analýzy ===
Nederministický PDA => nedeterministický algoritmus => exponenciální deterministický algoritmus

**Řešení:**
• deterministický algoritmus složitosti <math>O(n^{3})</math>, kde n = |w| (algoritmus Cocke -- Kasami -- Younger)
• deterministické zásobníkové automaty a deterministické bezkontextové jazyky
• lineární algoritmy pro speciální třídy deterministických bezkontextových jazyků

=== C - Y - K algoritmus (Cocke - Younger - Kasami) ==
**Problém:** Lze v dané gramatice v CNF vygenerovat dané slovo w?
**Řešení:** Pro každé podslovo u slova w spočítáme množinu <math>T_{u}</math> všech neterminálů, z kterých lze odvodit u.
* u = a
* u = ab
* u = abc
<math>T_{i, j} = \{ X| X \Rightarrow^{*} w_{i}w_{i+1}...w_{i+j}w_{i+j-1}\}</math>
  * **Kubická složitost** vzhledem k délce vstupního slova (velikost tabulky: <math>\frac{n^{2}}{2}</math>, na vyplnění políčka je zapotřebí až n kroků.
  * Pracuje pouze s gramatikou v CNF (Chomského normální formě)
== Algoritmus: ==
<box 95% round orange|Algoritmus C - Y - K>**Vstup:** gramatika <math>G = (N, \Sigma, P, S)</math> v CNF, slovo <math>w = w_{1}...w_{n}</math>
Poznámka: <math>T_{i,j} = {X | X \rightarrow^{*} w_{i}...w_{i+j-1}}</math>
for i:=1 to n do
<math>T_{i,1} := \bot</math>
for každé pravidlo <math>A \rightarrow a \in P</math> do
if <math>a = w_{i}</math> then <math>T_{i,1} := T_{i,1} \cup \lbrace A \rbrace</math> fi
od od
for j:=2 to n do 
for i:=1 to n-j+1 do
<math>T_{i,j}:= \bot</math>
for k:=1 to j-1 do
for každé pravidlo <math>A \rightarrow BC \in P</math> do
if <math>B \in T_{i, k} \wedge C \in T_{i+k, j-k}</math> then <math>T_{i, j}:= T_{i, j} \cup</math> {A} fi

od od od od</box>

== Příklad ==
Je dána bezkontextová gramatika G = ({S,A,B,C}, {a, b, c, d}, P, S) v CNF, kde
P = { S -> AA | BC | a | b,
A -> BA | BB | a | c,
B -> AB | CA | b,
C -> BC | CC | SC | d }
Syntaktická analýza slova <math>acddbba</math> pomocí C-K-Y algoritmu:

{{:home:inf:pda_cyk.png}}

Vidíme, že <math>S \in T_{1,7} = {S,B,A}</math>, tedy <math>acddbba \in L(G)</math>. 

== Intuitivní návod na vyplňování tabulky: ==
  - na nultý řádek napíšeme slovo, které chceme testovat (co sloupeček, to 1 terminál)
  - obsah každého políčka v 1. řádku tvoří **množina** neterminálů, ze kterých se vygenerují terminály v příslušném sloupečku nultého řádku
  - další řádky se vyplňují stylem, který je naznačený u žlutého políčka: do množiny v políčku se zapíší všechny neterminály, které generují všechny dvojice neterminálů z příslušných dvojic políček - každá používaná dvojice políček je orámovaná stejnou barvou.
Pro žluté políčko vezmeme jednu z dvojic políček - např. tu orámovanou zeleně. Vzniklé dvojice neterminálů jsou SB a AB. SB není generována žádným neterminálem, tedy do žlutého políčka nepřipisuju nic. AB je generovaná B, proto B zapíšu do žlutého políčka. Stejně postupuju i u ostatních dvojic políček. 
    * Možnost, jak vybírat správné dvojice políček: začínám políčkem, které je nejníž v příslušném sloupečku a políčkem, který je nejblíž v úhlopříčce směrem doprava (pro žluté políčko to jsou zelené rámečky) a dál postupuju (podle krásně jednoduchého návodu Vaška Brožka:), tak že lezu nahoru po žebříku (ve sloupečku) a sestupuju po schodech (v úhlopříčce).

===== Předměty =====
[[https://is.muni.cz/auth/predmety/predmet.pl?id=454974;| IB102 Automaty a gramatiky]]
[[https://is.muni.cz/auth/predmety/predmet.pl?id=427603;|IB005 Formální jazyky a automaty I]]

===== Literatura =====
Skripta Formální jazyky a automaty I
Slajdy k přednáškám IB102 na [[http://www.fi.muni.cz/~xstrejc/IB102/|stránkách Jana Strejčka]]

===== Vypracoval =====

Didl - Dita Dlabolová
Stav: 100%, z mé strany hotovo a zkontrolováno.

FIXME Je potřeba ještě zapracovat [[http://statnice.dqd.cz/tmp/zasobnikove_automaty_syn_analyza.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~