====== Zásobníkové automaty ====== 
[[wp>Pushdown automaton]]

//M// = (//Q//, //Σ//, //Γ//, //δ//, //q//₀, //Z//₀, //F//)
  * //Q// – konečná množina stavů
  * //Σ// – konečná vstupní abeceda
  * //Γ// – konečná zásobníková abeceda
  * //δ// – přechodová funkce ve tvaru //δ//: //Q// × (//Σ// ∪ {//ε//}) × //Γ// → 2<sup>//Q// × //Γ//*</sup>
  * //q//₀ ∈ //Q// – počáteční stav
  * //Z//₀ ∈ //Γ// – počáteční symbol zásobníku
  * //F// ⊆ //Q// – množina koncových stavů
===== Jazyky přijímané ZA =====
Bezkontextové jazyky

==== Syntaktická analýza ====
=== Shora dolů ===
[[wp>Top-down parsing]]

Přijímá prázdným zásobníkem!

//P// = ({//q//}, //Σ//, //N// ∪ //Σ//, //δ//, //q//, //S//, ∅)
  * Je-li //A// → //α// pravidlo z //P//, pak //δ//(//q//, //ε//, //A//) ∋ (//q//, //α//)
  * //δ//(//q//, //a//, //a//) = {(//q//, //ε//)} pro všechna //a// ∈ //Σ//

=== Zdola nahoru ===
[[wp>Bottom-up parsing]]

Vyžaduje rozšířený zásobníkový automat!

//P// = ({//q//, //r//}, //Σ//, //N// ∪ //Σ// ∪ {//#//}, //δ//, //q//, //#//, {//r//})
  - Redukce: Je-li //A// → //α// pravidlo z //P//, pak  //δ//(//q//, //ε//, //α//) ∋ (//q//, //A//)
  - Shift: //δ//(//q//, //a//, //ε//) = {(//q//, //a//)} pro všechna //a// ∈ //Σ//
  - Accept: //δ//(//q//, //ε//, //S#//) = {(//r//, //ε//)}
===== Varianty ZA =====
==== Determinsitický zásobníkový automat ====
[[wp>Deterministic pushdown automaton]]

Automat je deterministický, pokud jsou splněný obě podmínky:
  * ∀//q// ∈ //Q//, //a// ∈ //Σ// ∪ {//ε//}, //x// ∈ //Γ//: |//δ//(//q//, //a//, //x//)| ≤ 1\\ Existuje maximálně 1 přechod pro každou //δ//.
  * ∀//q// ∈ //Q//, //x// ∈ //Γ//: pokud //δ//(//q//, //ε//, //x//) ≠ ∅, pak //δ//(//q//, //a//, //x//) = ∅ pro //a// ∈ //Σ//\\ Můžu mít přechod který nic nečte ze vstupu při daném vrcholu zásobníku, ale pak nesmím mít se stejným vrcholem zásobníku přechod který by něco četl. Proste to musí být jednoznačné!

Jiný zápis toho samého (je tam hezká symetrie):
  * ∀//a// ∈ //Σ//: |//δ//(//q//, //a//, //z//)| ≤ 1 ∧ //δ//(//q//, //ε//, //x//) = ∅, nebo
  * ∀//a// ∈ //Σ//: //δ//(//q//, //a//, //z//) = ∅ ∧ |//δ//(//q//, //ε//, //x//)| ≤ 1

==== Rozšířený zásobníkový automat ====
//δ//: //Q// × (//Σ// ∪ {//ε//}) × //Γ//* → 2<sup>//Q// × //Γ//*</sup>

Rozdíl je v //Γ//*, automat tedy může číst 0–//n// symbolů ze sásobníku.