Formal grammar

G = (N, Σ, P, S)

• N – konečná množina neterminálů
• Σ – konečná množina terminálů, disjunktní s N
• P – přepisovací pravidla, obecně ve tvaru (Σ ∪ N)* N (Σ ∪ N)* → (Σ ∪ N)*
• S ∈ N – startovací symbol

Podle tvaru P se rozlišují třídy gramatik.

Formal language

• Konkatenace (zřetězení): L₁ · L₂ = {xy | x ∈ L₁, y ∈ L₂}
• Iterace a pozitivní iterace:
  • L⁰ = {ε}
  • Lⁿ = L · Lⁿ⁻¹ pro n ≥ 1
  • L* = ∪ Lⁿ pro pro n ≥ 0
  • L⁺ = ∪ Lⁿ pro pro n ≥ 1
• Doplněk: L′ = Σ* \ L
• Průnik: L₁ ∩ L₂ = {w | w ∈ L₁ ∧ w ∈ L₂}
• Sjednocení: L₁ ∪ L₂ = {w | w ∈ L₁ ∨ w ∈ L₂}

Regular language

Regular grammar

Viz gramatika.

Rozlišujeme pravou a levou lineární, podle pozice neterminálu na pravé straně pravidel (v příkladu je pravá):

• A → xB; A, B ∈ N, x ∈ Σ*
• A → x; x ∈ Σ*

Rozlišujeme pravou a levou regulární:

• A → xB; A, B ∈ N, x ∈ Σ
• A → x; x ∈ Σ
• S → ε, pokud se S neobjevuje na pravé straně žádného pravidla

Finite-state machine

M = (Q, Σ, δ, q₀, F)

• Q – konečná množina stavů
• Σ – konečná vstupní abeceda
• δ – přechodová funkce ve tvaru δ: Q × Σ → 2^Q1)
• q₀ ∈ Q – počáteční stav
• F ⊆ Q – množina koncových stavů

• Konfigurace: C = (q, w), (q, w) ∈ Q × Σ* (Prostě stav ve kterém se automat právě nachází a co má ještě přečíst.)
• Přechod automatu: binární relace ⊢ ⊆ (Q × Σ*) × (Q × Σ*)
  • (q, w) ⊢ (q′, w′) ⇔ w = aw′ ∧ q′ ∈ δ(q, a) pro q, q′ ∈ Q; a ∈ Σ; w, w′ ∈ Σ*

Pouze se změní δ: Q × Σ → Q ∪ {nedef}, nedef ∉ Q.

Stejný jako deterministický, ale neobsahuje nedef, protože δ: Q × Σ → Q musí platit pro všechny Q × Σ.

Pumping lemma for regular languages

∃p > 0: ∀w ∈ L: |w| ≥ p ⇒ ∃x, y, z ∈ Σ*:

• w = xyz ∧
• 0 < |y| ≤ p ∧
• ∀i ≥ 0: xyⁱz ∈ L

Dokazuje se sporem.

Pumping lemma je podmínka nutná, nikoliv dostačující. Takže s ní dokážete, že jazyk není ragulární, ale na důkaz že regulární je nestačí. Jak tedy dokázat regulárnost? Třeba sestavit automat.

• Problém neprázdnosti: L ≠ ∅
• Problém náležitosti: w ∈ L
• Problém ekvivalence: L(G₁) = L(G₂)

Context-free language

Context-free grammar

Viz gramatika.

Bezkontextová gramatika má konečnou množinu přepisovacích pravidel P, tvaru:

• A → α, A ∈ N, α ∈ (N ∪ Σ)*

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^{Q × Γ*}
• q₀ ∈ Q – počáteční stav
• Z₀ ∈ Γ – počáteční symbol zásobníku
• F ⊆ Q – množina koncových stavů

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

δ: Q × (Σ ∪ {ε}) × Γ* → 2^{Q × Γ*}

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

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 ∈ Σ

Bottom-up parsing

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

P = ({q, r}, Σ, N ∪ Σ ∪ {#}, δ, q, #, {r})

1. Redukce: Je-li A → α pravidlo z P, pak δ(q, ε, α) ∋ (q, A)
2. Shift: δ(q, a, ε) = {(q, a)} pro všechna a ∈ Σ
3. Accept: δ(q, ε, S#) = {(r, ε)}

Pumping lemma for context-free languages

Nechť L je bezkontextový jazyk. Pak existuje konstanta k > 0 taková, že je-li z ∈ L a |z| ≥ k, pak lze z zapsat ve tvaru: z = uvwxy, vx ≠ ε, |vwx| ≤ k a pro všechna i ≥ 0 je uvⁱwxⁱy ∈ L.

Opět platí to samé, co u regulárních jazyků.

• Problém neprázdnosti jazyka
• Probém příslušnosti řetězce w ∈ Σ* do jazyka
• Problém konečnosti jazyka

• Problém ekvivalence jazyků bezkontextových gramatik
• Problém inkluze jazyků bezkontextových gramatik

Turing machine

M = (Q, Σ, Γ, δ, q₀, q_F)

• Q – konečná množina stavů
• Σ – konečná vstupní abeceda, Δ ∉ Σ
• Γ – konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ
• δ – parciální přechodová funkce, δ: (Q \ {q_F}) × Γ → Q × (Γ ∪ {L, R}), kde L, R ∉ Γ
• q₀ – počáteční stav, q₀ ∈ Q
• q_F – koncový stav, q_F ∈ Q

Jestli má stroj více pásek, nebo je nedeterministický nijak nezvětšuje jeho schopnost přijímat jazyky!

Je-li L libovolný jazyk z NP, pak je redukovatelný na SAT problém.

Důkaz: Protože L ∈ NP, exsituje nedeterministický Turingův stroj M a polynom p(x) tak, že pro každé w ∈ L stroj M přijímá maximálně v p(|w|) krocích. Jádro důkazu tvoří konstrukce polynomiální redukce f z L na L_SAT: Pro každý řetězec w ∈ L bude f(w) množina klauzulí, které jsou splnitelné, právě když M přijímá w.