G = (N, Σ, P, S)
Podle tvaru P se rozlišují třídy gramatik.
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í:
M = (Q, Σ, δ, q₀, F)
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 ∈ Σ*:
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.
Sjednocení (∪) | ✔ |
---|---|
Průnik (∩) | ✔ |
Konkatenace (•) | ✔ |
Iterace (*) | ✔ |
Doplněk (‾) | ✔ |
Reverze (ᴿ) | ✔ |
Substituce | ✔ |
Morfismus | ✔ |
Inverzní morfismus | ✔ |
Viz gramatika.
Bezkontextová gramatika má konečnou množinu přepisovacích pravidel P, tvaru:
M = (Q, Σ, Γ, δ, q₀, Z₀, F)
Deterministic pushdown automaton
Automat je deterministický, pokud jsou splněný obě podmínky:
Jiný zápis toho samého (je tam hezká symetrie):
δ: Q × (Σ ∪ {ε}) × Γ* → 2Q × Γ*
Rozdíl je v Γ*, automat tedy může číst 0–n symbolů ze sásobníku.
Přijímá prázdným zásobníkem!
P = ({q}, Σ, N ∪ Σ, δ, q, S, ∅)
Vyžaduje rozšířený zásobníkový automat!
P = ({q, r}, Σ, N ∪ Σ ∪ {#}, δ, q, #, {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ů.
Sjednocení (∪) | ✔ |
---|---|
Průnik (∩) | ✘2) |
Konkatenace (•) | ✔ |
Iterace (*) | ✔ |
Doplněk (‾) | ✘ |
Reverze (ᴿ) | ✔ |
Substituce | ✔ |
Morfismus | ✔ |
Inverzní morfismus | ✔ |
Když jde něco vyčíslit, jde to udělat Turingovým strojem.
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
Kontextové | Rekurzivní | Rekurzivně vyčíslitelné | |
---|---|---|---|
Sjednocení (∪) | ✔ | ✔ | ✔ |
Průnik (∩) | ✔ | ✔ | ✔ |
Konkatenace (•) | ✔ | ✔ | ✔ |
Iterace (*) | ✔ | ✔ | ✔ |
Doplněk (‾) | ✔ | ✔ | ✘ |
Reverze (ᴿ) | ✔ | ✔ | ✔ |
Substituce | ✘ | ✘ | ✔ |
Morfismus | ✘ | ✘ | ✔ |
Inverzní morfismus | ✔ | ✔ | ✔ |
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 LSAT: Pro každý řetězec w ∈ L bude f(w) množina klauzulí, které jsou splnitelné, právě když M přijímá w.
Zastaví daný TS pro daný vstup? Je to částečně rozhodnutelný problém.
Důkaz:
bool halt(machine M, data w) { if (M(w).finished) { return true; } else { return false; } }
void paradox(x) { if (halt(x, x)) { while (true); } else { return; } }
paradox(paradox)
?halt(paradox, paradox) == true
.paradox(paradox)
zacyklí. Víme ale, že pokud se paradox(paradox)
zacyklí, pak halt(paradox, paradox) == false
, což je spor!halt(paradox, paradox) == false
.paradox(paradox)
zastaví. Víme ale, že pokud se paradox(paradox)
zastaví, pak halt(paradox, paradox) == true
, což je také spor!halt
nemůže existovat.halt
odpovědět true
, tak to dokáže vždy, tudíž je HP částečně rozhodnutelný.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:
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) ∈ ℕᵏ
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í.
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]
Funkce, které můžeme simulovat na 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í.
Sestaví funkce pro jednotlivé funkce TS a to pro mov
, sym
, state
, cursym
, nexthead
, nextstate
, nexttape
a stoptime