====== Tahák ====== ===== Půlsemestrálka ===== ==== Gramatika ==== [[wp>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 ==== [[wp>Formal_language#Operations_on_languages|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 ==== [[wp>Regular language]] === Gramatika === [[wp>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 === [[wp>Finite-state machine]] //M// = (//Q//, //Σ//, //δ//, //q//₀, //F//) * //Q// – konečná množina stavů * //Σ// – konečná vstupní abeceda * //δ// – přechodová funkce ve tvaru //δ//: //Q// × //Σ// → 2^//Q//(([[wp>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 === [[wp>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 ==== [[wp>Context-free language]] === Gramatika === [[wp>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 === [[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^{//Q// × //Γ//*} * //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 == [[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^{//Q// × //Γ//*} Rozdíl je v //Γ//*, automat tedy může číst 0–//n// symbolů ze sásobníku. === 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//, //ε//)} === Pumping lemma === [[wp>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í [[#pumping_lemma|to samé, co u regulárních jazyků]]. === Uzávěrové vlastnosti === ^ Sjednocení (∪) | ✔ | ^ Průnik (∩) | ✘((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álka|půlsemestrálce]]! ==== Churchova teze ==== [[wp>Church–Turing thesis]] Když jde něco vyčíslit, jde to udělat Turingovým strojem. ==== Turingovy stroje ==== [[wp>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! Turingův stroj se nazývá úplný, když pro každý vstup zastaví (tzn. že se nezacyklí). * Úplný Turingův stroj ⇔ rekurzivní jazyk * Turingův stroj ⇔ rekurzivně vyčíslitelný jazyk 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ý LOL * čá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 [[wp>Boolean satisfiability problem|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//. ==== Halting problem ==== [[wp>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é funkce ==== [[wp>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//₂, …, //x_n//) ∈ ℕᵏ === Primitivně rekurzivní funkce === [[wp>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 == - nulová funkce: ξ() = 0 - fce následníka: σ(//x//) = //x// + 1 - fce projekce: πⁿ_//k//: ℕ^//n// → ℕ (vybírá k-tou složku z n-tice) == Základní funkce vytvořené z počátečních == - kombinace //f// × //g//: - ℕᵏ → ℕⁿ⁺ᵐ - //f// × //g//(//x//) = (//f//(//x//′), //g//(//x//′)), //x// ∈ ℕᵏ - kompozice //g// ∘ //f//(//x//) = //g//(//f//(//x//′)), //x// ∈ ℕᵏ - primitivní rekurze: - //f//(//x//′, 0) = //g//(//x//′) - //f//(//x//′, //y// + 1) = //h//(//x//′, //y//, //f//(//x//′, //y//)), //x// ∈ ℕᵏ === Parcialně neboli rekurzivní funkce === [[wp>μ-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: * //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é funkce === Funkce, které můžeme simulovat na TS. == Turingovsky vyčíslitelné parciální rekurzivní funkce == - Najdeme TS simulující počáteční funkce - Najdeme TS simuljící primitivně rekurzivní funkce - 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''