Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- tin:pulsemestralka [01. 01. 2012, 12.59:54] – [Turingovy stroje] bugfix beny
+++ tin:pulsemestralka [02. 08. 2026, 13.51:45] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== 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<sup>//Q//</sup>(([[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<sup>//Q// × //Γ//*</sup>
-  * //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<sup>//Q// × //Γ//*</sup>
-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 =====
-<note important>Vědět i to, co bylo na [[#půlsemestrálka|půlsemestrálce!]]</note>
-==== Turingovy stroje ====
-[[wp>Turing machine]]
-//M// = (//Q//, //Σ//, //Γ//, //δ//, //q//₀, //q<sub>F</sub>//)
-  * //Q// -- konečná množina stavů
-  * //Σ// -- konečná vstupní abeceda, //Δ// ∉ //Σ//
-  * //Γ// -- konečná pásková abeceda, //Σ// ⊂ //Γ//, //Δ// ∈ //Γ//
-  * //δ// -- parciální přechodová funkce, //δ//: (//Q// \ {//q<sub>F</sub>//}) × //Γ// → //Q// × (//Γ// ∪ {//L//, //R//}), kde //L//, //R// ∉ //Γ//
-  * //q//₀ -- počáteční stav, //q//₀ ∈ //Q//
-  * //q<sub>F</sub>// -- koncový stav, //q<sub>F</sub>// ∈ //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ý 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<sub>SAT</sub>//: Pro každý řetězec //w// ∈ //L// bude //f//(//w//) množina klauzulí, které jsou splnitelné, právě když //M// přijímá //w//.

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku