Tahák

Půlsemestrálka

Gramatika

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.

Operace nad jazyky

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₂}

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á):

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

Konečný automat

Finite-state machine

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

Q – konečná množina stavů

Σ – konečná vstupní abeceda

δ – přechodová funkce ve tvaru δ: Q × Σ → 2Q1)Power set , potenční množina

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

Deterministický konečný automat

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

Ú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: ∀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.

Uzávěrové vlastnosti

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

Rozhodnutelné problémy

Problém neprázdnosti: L ≠ ∅

Problém náležitosti: w ∈ L

Problém ekvivalence: L(G₁) = L(G₂)

Bezkontextové jazyky

Context-free language

Gramatika

Context-free grammar

Viz gramatika.

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

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

Zásobníkový automat

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 × (Σ ∪ {ε}) × Γ → 2Q × Γ*

q₀ ∈ Q – počáteční stav

Z₀ ∈ Γ – počáteční symbol zásobníku

F ⊆ Q – množina koncových stavů

Determinsitický zásobníkový automat

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 × (Σ ∪ {ε}) × Γ* → 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, ∅)

Je-li A → α pravidlo z P, pak δ(q, ε, A) ∋ (q, α)

δ(q, a, a) = {(q, ε)} pro všechna a ∈ Σ

Zdola nahoru

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, ε)}

Pumping lemma

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ů.

Uzávěrové vlastnosti

Sjednocení (∪)	✔
Průnik (∩)	✘2) Jsou uzavřené pouze na průnik s regulárními jazyky
Konkatenace (•)	✔
Iterace (*)	✔
Doplněk (‾)	✘
Reverze (ᴿ)	✔
Substituce	✔
Morfismus	✔
Inverzní morfismus	✔

Rozhodnutelné problémy

Problém neprázdnosti jazyka

Probém příslušnosti řetězce w ∈ Σ* do jazyka

Problém konečnosti jazyka

Nerozhodnutelné problémy

Problém ekvivalence jazyků bezkontextových gramatik

Problém inkluze jazyků bezkontextových gramatik

Semestrálka

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

Churchvoa 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)

Q – konečná množina stavů

Σ – konečná vstupní abeceda, Δ ∉ Σ

Γ – konečná pásková abeceda, Σ ⊂ Γ, Δ ∈ Γ

δ – parciální přechodová funkce, δ: (Q \ {qF}) × Γ → Q × (Γ ∪ {L, R}), kde L, R ∉ Γ

q₀ – počáteční stav, q₀ ∈ Q

qF – koncový stav, qF ∈ Q

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í).

Jazyk se nazývá rekurzivní, když ho přijímá úplný Turingův stroj, a rekurzivně vyčíslitelný, pokud ho přijímá nějaký Turingův stroj.

Problém může být:

rozhodnutelný – pokud jeho jazyk je rekurzivní, čili pokud ho rozhodne (dokáže říct ano/ne) nějaký úplný TS.

nerozhodnutelný – pokud není rozhodnutelný

částečně rozhodnutelný – pokud je jeho jazyk rekurzivně vyčíslitelný, tzn. existuje TS který dokáže říct vždy ano, ale pro některé případy kdy by měl říct ne se zacyklí (plyne z definice rekurzivně vyčíslitelného jazyka)

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 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.

Halting problem

Halting problem

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

Důkaz:

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; } }

Zkonstrujeme program

void paradox(x) { if (halt(x, x)) { while (true); } else { return; } }

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!

V obou případech jsme došli ke sporu, tudíž program halt nemůže existovat.

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:

Není-li jazyk A rekurzivně vyčíslitelný, pak ani jazyk B není rekurzivně vyčíslitelný.

Není-li jazyk A rekurzivní, pak ani jazyk B není rekurzivní.

Je-li jazyk A rekurzivně vyčíslitelný, pak i jazyk B je rekurzivně vyčíslitelný.

Je-li jazyk A rekurzivní, pak i jazyk B je rekurzivní.

Vyčíslitelné fce

Funkce, které je možné spočítat v obecném smysli 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).

x = (x1,x2,…,xn) ∈ ℕk

Počáteční fce

nulová funkce: ξ() = 0

fce následníka: σ (x) = x + 1

fce projekce: πnk: ℕn⟶ℕ (vybírá k-tou složku z n-tice)

Primitivně rekurzivní fce

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

kombinace f×g:

Nk⟶Nn+m

f×g(x) = (f(x), g(x)), x ∈ ℕk

kompozice g ○ f(x) = g(f(x)), x ∈ ℕk

primitivní rekurze:

f(x,0) = g(x)

f(x,y+1) = h(x,y,f(x,y)), x ∈ ℕk

Parcialně rekurzivní fce

Zavedeme techniku takzvané minimalizace, které umožnuje vytvořit fci f: ℕn ⟶ ℕ z jiné fce g: ℕn+1 ⟶ ℕ kde f(x) je nejmenší y takové, že:

y(x,y) = 0

y(x, z) je definována pro ∀z < y, z ∈ ℕ

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

Turingovsky vyčíslitelné fce

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

Turingovsky vyčíslitelné parciální rekurzivní fce

Najdeme TS simulující počáteční fce

Najdeme TS simuljící primitivně rekurzivní fce

Najdeme TS simlujicí minimalizaci

Fce pomocí TS

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

TS pomocí fcí

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