Obsah

Tahák

Půlsemestrálka

Gramatika

Formal grammar

G = (N, Σ, P, S)

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

Operace nad jazyky

Formal language

Regulární jazyky

Regular language

Gramatika

Regular grammar

Viz gramatika.

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

Rozlišujeme pravou a levou regulární:

Konečný automat

Finite-state machine

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

Deterministický konečný automat

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

Úplně definovaný konečný automat

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

Pumping lemma

Pumping lemma for regular languages

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

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.

Uzávěrové vlastnosti

Sjednocení (∪)
Průnik (∩)
Konkatenace (•)
Iterace (*)
Doplněk (‾)
Reverze (ᴿ)
Substituce
Morfismus
Inverzní morfismus

Rozhodnutelné problémy

Bezkontextové jazyky

Context-free language

Gramatika

Context-free grammar

Viz gramatika.

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

Zásobníkový automat

Pushdown automaton

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

Determinsitický zásobníkový automat

Deterministic pushdown automaton

Automat je deterministický, pokud jsou splněný obě podmínky:

Jiný zápis toho samého (je tam hezká symetrie):

Rozšířený zásobníkový automat

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

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

Syntaktická analýza

Shora dolů

Top-down parsing

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

P = ({q}, Σ, NΣ, δ, q, S, ∅)

Zdola nahoru

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

Pumping lemma for context-free languages

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

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

Uzávěrové vlastnosti

Sjednocení (∪)
Průnik (∩) 2)
Konkatenace (•)
Iterace (*)
Doplněk (‾)
Reverze (ᴿ)
Substituce
Morfismus
Inverzní morfismus

Rozhodnutelné problémy

Nerozhodnutelné problémy

Semestrálka

Vědět i to, co bylo na půlsemestrálce!

Churchova teze

Church–Turing thesis

Když jde něco vyčíslit, jde to udělat Turingovým strojem.

Turingovy stroje

Turing machine

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

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

Turingův stroj se nazývá úplný, když pro každý vstup zastaví (tzn. že se nezacyklí).

Problém může být:

TS jsou ekvivalentní s gramatikami typu 0 (rekurzivně vyčíslitelné).

Speciálním případem TS jsou linárně omezené automaty (LOA), je to vlastně TS ale s konečnou páskou, a dokáží přijímat kontextové jazyky

Uzávěrové vlastnosti

Kontextové Rekurzivní Rekurzivně vyčíslitelné
Sjednocení (∪)
Průnik (∩)
Konkatenace (•)
Iterace (*)
Doplněk (‾)
Reverze (ᴿ)
Substituce
Morfismus
Inverzní morfismus

Cookův teorém

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

Důkaz: Protože LNP, exsituje nedeterministický Turingův stroj M a polynom p(x) tak, že pro každé wL 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 LSAT: Pro každý řetězec wL bude f(w) množina klauzulí, které jsou splnitelné, právě když M přijímá w.

Halting problem

Halting problem

Zastaví daný TS pro daný vstup? Je to částečně rozhodnutelný problém.

Důkaz:

  1. Předpokládejme, že problém je řešitelný. Tzn. existuje program
    bool halt(machine M, data w) {
    	if (M(w).finished) {
    		return true;
    	} else {
    		return false;
    	}
    }
  2. Zkonstrujeme program
    void paradox(x) {
    	if (halt(x, x)) {
    		while (true);
    	} else {
    		return;
    	}
    }
  3. Co se stane, pokud zavoláme paradox(paradox)?
    • Předpokládejme, že halt(paradox, paradox) == true.
      • Pak se tedy paradox(paradox) zacyklí. Víme ale, že pokud se paradox(paradox) zacyklí, pak halt(paradox, paradox) == false, což je spor!
    • Předpokládejme, že halt(paradox, paradox) == false.
      • Pak se tedy paradox(paradox) zastaví. Víme ale, že pokud se paradox(paradox) zastaví, pak halt(paradox, paradox) == true, což je také spor!
  4. V obou případech jsme došli ke sporu, tudíž program halt nemůže existovat.
  5. Je ale zřejmé, že pokud má halt odpovědět true, tak to dokáže vždy, tudíž je HP částečně rozhodnutelný.

Redukce

Je to technika dokazování, kdy nalezneme algoritmický převod z jednoho problému, na problém druhý, kdy o druhém víme zda je nebo není rozhodnutelný.

Protože lze problémy specifikovat jako jazyky, jde vlastně o převod mezi jazyky, a platí že:

  1. Není-li jazyk A rekurzivně vyčíslitelný, pak ani jazyk B není rekurzivně vyčíslitelný.
  2. Není-li jazyk A rekurzivní, pak ani jazyk B není rekurzivní.
  3. Je-li jazyk A rekurzivně vyčíslitelný, pak i jazyk B je rekurzivně vyčíslitelný.
  4. Je-li jazyk A rekurzivní, pak i jazyk B je rekurzivní.

Vyčíslitelné funkce

Computable function

Funkce, které je možné spočítat v obecném smyslu bez ohledu na výpočetní systém. Existují totální funkce (pokrývají celý obor hodnot) a striktně parciální (nejsou pro některé hodnoty definovány, např div).

I o TS můžeme uvažovat jako o funkcích. Úplný TS je totální funkce, obyčejný TS je parciální funkce (pokud se zacyklí, funkce není definovaná).

x′ = (x₁, x₂, …, xn) ∈ ℕᵏ

Primitivně rekurzivní funkce

Primitive recursive function

Třída primitivně rekurzivních funkcí obsahuje funkce, které lze sestrojit pomocí počátečních funkcí a kombinace, kompozice a primitivní rekurze. Každá funkce v této třídě je totální.

Počáteční funkce
  1. nulová funkce: ξ() = 0
  2. fce následníka: σ(x) = x + 1
  3. fce projekce: πⁿk: ℕn → ℕ (vybírá k-tou složku z n-tice)
Základní funkce vytvořené z počátečních
  1. kombinace f × g:
    1. ℕᵏ → ℕⁿ⁺ᵐ
    2. f × g(x) = (f(x′), g(x′)), x ∈ ℕᵏ
  2. kompozice gf(x) = g(f(x′)), x ∈ ℕᵏ
  3. primitivní rekurze:
    1. f(x′, 0) = g(x′)
    2. f(x′, y + 1) = h(x′, y, f(x′, y)), x ∈ ℕᵏ

Parcialně neboli rekurzivní funkce

μ-recursive function

Zavedeme techniku takzvané minimalizace, které umožnuje vytvořit funkci f: ℕⁿ → ℕ z jiné funkce g: ℕⁿ⁺¹ → ℕ kde f(x′) je nejmenší y takové, že:

Zapisujeme ji pak f(x′) = µy[g(x′, y) = 0]

Turingovsky vyčíslitelné funkce

Funkce, které můžeme simulovat na TS.

Turingovsky vyčíslitelné parciální rekurzivní funkce
  1. Najdeme TS simulující počáteční funkce
  2. Najdeme TS simuljící primitivně rekurzivní funkce
  3. Najdeme TS simlujicí minimalizaci
Funkce pomocí TS

Parametry funkce můžeme hodit na pásku TS a odělit pomocí Δ. Pokud po provedení výpočtu bude na pásce výsledek funkce pro tyto parametry, TS přijme. Pokud není pro dané parametry funkce definována, TS cyklí.

TS pomocí funkcí

Sestaví funkce pro jednotlivé funkce TS a to pro mov, sym, state, cursym, nexthead, nextstate, nexttape a stoptime

1)
Power set, potenční množina
2)
Jsou uzavřené pouze na průnik s regulárními jazyky