Rozdíly

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

--- msz:gramatiky [17. 06. 2012, 11.59:13] – [Typ 1 – kontextové gramatiky] wiki pitel
+++ msz:gramatiky [02. 08. 2026, 23.02:18] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Klasifikace gramatik, formálních jazyků a automatů přijímajících jazyky ======
-===== Základní pojmy =====
-  * **Abeceda //Σ//**
-    * Neprázdná množina, jejíž prvky nazýváme symboly.
-  * **Řetezec** / **slovo** / **věta //w//**
-    * Konečná posloupnost symbolů abecedy.
-    * Alternativní definice:
-      - Prázdný řetezec je řetezec.
-      - Je-li //w// řetězec a //a// symbol abecedy pak //wa// je řetezec.
-      - Řetězce jsou vše, co lze získat jen a pouze aplikací předchozích pravidel
-  * **Prázdný řetezec ε**
-    * Řetezec neobsahující žádný symbol
-  * **Konkatenace //xy// (někdy //x.y//)**
-    * Připojení řetezce za jiný řetezec
-    * Konkatenace je asociativní
-    * Prázdný řetezec je neutrální prvek vzhledem ke konkatenaci
-  * **Iterace //Σ//<sup>*</sup>**
-    * Množina všech řetězců nad abecedou //Σ//.
-    * Volný monoid nad abecedou //Σ// generovaný operací konkatenace.
-  * **Pozitivní iterace //Σ//⁺**
-    * Iterace bez prázdného řetezce
-  * **Formální jazyk //L//**
-    * Jakákoli podmnožina //L// ⊆ //Σ//<sup>*</sup>.
-  * **Konkatenace jazyků**
-    * Rozumíme binární operaci //L//₁ . //L//₂ = {//xy// | //x// ∈ //L//₁ ∧ //y// ∈ //L//₂}
-  * **Iterace jazyka**
-    * //L//⁰ = {//ε//}
-    * //Lⁿ// = //L// . //Lⁿ//⁻¹, //n// ≥ 1
-    * //L//<sup>*</sup> = ∪ //Lⁿ//, //n// ≥ 0
-    * //L//⁺ = ∪ //Lⁿ//, //n// ≥ 1
-===== Gramatika =====
-**Gramatika** //G// = (//N//, //Σ//, //P//, //S//)
-  * //N// -- konečná množina nonterminálních symbolů (**nonterminálů**)
-  * //Σ// --  konečná množina terminálních symbolů (**terminálů**)
-  * //P// -- je konečná množina **přepisovacích pravidel**
-  * //S// -- **počáteční nonterminál** //S// ∈ //N//
-  * **Přepisovací pravidlo**
-    * Podmnožina kartézského součinu (//N// ∪ //Σ//)<sup>*</sup>//N//(//N// ∪ //Σ//)<sup>*</sup> × (//N// ∪ //Σ//)<sup>*</sup>
-    * (//a//, //b//) ∈ //P// zapisujeme ve tvaru //a// -> //b//, kde //a// je levá strana a //b// je pravá strana pravidla.
-  * **Přímá derivace =>**
-    * Binární relace mezi řetezci //u// a //v// která platí pokud můžeme řetezce zapsat jako //u// = //gad//, //v// = //gbd// a (//a//, //b//) ∈ //P//, tj. pokud lze řetězec //v// vytvořit z retězce //u// aplikací jednoho přepisovacího pravidla.
-  * **Derivace =>⁺**
-    * Tranzitivní uzávěr relace přímé derivace, tj. pokud lze vytvořit řetězec //v// z řetězce //u// postupnou aplikací několika přepisovacích pravidel.
-  * **Derivace =><sup>*</sup>**
-    * Tranzitivní a reflexivní uzávěr relace přímé derivace, tj. pokud lze vytvořit řetězec //v// z řeťazca //u// postupnou aplikací několika přepisovacích pravidel nebo pokud jsou řetězce stejné.
-  * **Větná forma**
-    * Řetězec terminálů a nonterminálů, které jsou derivací počátečního nontermínálu
-  * **Věta**
-    * Větná forma obsahující pouze terminály
-  * **Jazyk generovaný gramatikou**
-    * Množina všech vět, které patří do gramatiky //L//(//G//) = {//w// | //S// =><sup>*</sup> //w// ∧ //w// ∈ //Σ//<sup>*</sup>}
-===== Chomského hierarchie klasifikace gramatik =====
-Klasifikace je definována podle tvaru přepisovacích pravidel příslušných gramatik
-Platí: //L//₃ ⊂ //L//₂ ⊂ //L//₁ ⊂ //L//₀
-==== Typ 0 – obecné (neomezené) gramatiky ====
-  * Rekurzivně vyčíslitelné jazyky
-  * Turingovy stroje
-  * Tvar pravidel: //α// -> //β//
-    * //α// ∈ (//N// ∪ //Σ//)<sup>*</sup>//N//(//N// ∪ //Σ//)<sup>*</sup>
-    * //β// ∈ (//N// ∪ //Σ//)<sup>*</sup>
-==== Typ 1 – kontextové gramatiky ====
-[[wp>Context-sensitive grammar]]
-  * Kontextové jazyky
-  * Lineárně omezené Turingovy stroje
-  * //αAβ// -> //αγβ//, nebo //S// -> //ε// pokud //ε// ∈ //L// a //S// se nevyskytuje na pravé straně žádného pravidla
-    * //A// ∈ //N//
-    * //α//, //β// ∈ (//N// ∪ //Σ//)<sup>*</sup>
-    * //γ// ∈ (//N// ∪ //Σ//)⁺
-    * Nesmí dojít ke zkrácení větné formy
-==== Typ 2 – bezkontextové gramatiky ====
-[[wp>Context-free grammar]]
-  * Bezkontextové jazyky
-  * Zásobníkové automaty
-  * //A// -> //γ//
-    * //A// ∈ //N//
-    * //γ// ∈ (//N// ∪ //Σ//)<sup>*</sup>
-==== Typ 3 – pravé/levé linární gramatiky ====
-[[wp>Regular grammar]]
-  * Regulární jazyky
-  * Konečné automaty
-  * Pravá lineární: //A// -> //xB// nebo //A// -> //x//
-  * Levá lineární: //A// -> //Bx// nebo //A// -> //x//
-    * //A//, //B// ∈ //N//
-    * //x// ∈ Σ<sup>*</sup>
-==== Speciální podtypy gramatik ====
-=== Pravé/levé regulární gramatiky ===
-Stejné jako 3, ale //x// ∈ //Σ// (bez <sup>*</sup>).
-=== Lineární gramatiky ===
-Podmnožina gramatik typu 2
-  * //A// -> //xBy// nebo //A// -> //x//
-    * //A//, //B// ∈ //N//
-    * //x//, //y// ∈ //Σ//<sup>*</sup>
-=== Deterministické bezkontextové gramatiky ===
-Podmnožina typu 2, jazyky příjamné deterministickým zásobníkovým automatem.
-=== Rekurzivní gramatiky ===
-Podmnožina typu 0. Přijímají je **úplné TS** (TS, které pro každý vstup rozhodnou -- nikdy necyklí).
-Všechny kontextové jazyk jsou rekurzivní, ale ne všechny rekurzivní jazyky jsou kontextové.

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku