Rozdíly

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

--- msz:vlastnosti_jazyku [06. 06. 2012, 13.17:18] – [Typ 2 – Bezkontextové jazyky] pitel
+++ msz:vlastnosti_jazyku [17. 08. 2026, 09.18:07] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Vlastnosti formálních jazyků ======
-===== Uzavřenost jazyků vůči operacím =====
-  * **Substituce** -- každý symbol věty nahradíme za některou větu substitučního jazyka pro daný symbol (substituční jazyk je stejné třídy jako jazyk)
-  * **Morfismus** -- speciální případ substituce, kdy substituční jazyk má vždy jen jednu větu (symbol vždy nahrazujeme za jednu a tu samou větu)
-  * **Inverzní morfismus** -- je operace opačná k morfismu - tj. každá věta jazyka je nahrazena za symbol tak aby náhrada byla inverzní k nějakému morfismu
-Ostatní operace jsou obvyklé množinové operace.
-^  Jazyk  ^  Sjednocení  ^  Průnik  ^  Průnik s 3  ^  Konkatenace  ^  Iterace  ^  Doplněk  ^  Substituce  ^  Reverze  ^  Morfismus  ^  Inv. morfismus  ^
-^  3  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |
-^  2 (deterministické)  |  ✘  |  ✘  |  ✔  |  ✘  |  ✘  |  ✔  |  ✘  |  ✘  |  ✘  |  ✔  |
-^  2  |  ✔  |  ✘  |  ✔  |  ✔  |  ✔  |  ✘  |  ✔  |  ✔  |  ✔  |  ✔  |
-^  1  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |
-^  0 (rekurzivní)  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✘  |  ✔  |  ✘  |  ✔  |
-^  0  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✘  |  ✔  |  ✔  |  ✔  |  ✔  |
-===== Rozhodnutelnost problémů v jazycích =====
-  * **Neprázdnost** -- obsahuje jazyk alespoň jeden řetezec?
-  * **Prázdnost** -- jazyk neobsahuje žádný řetezec?
-  * **Konečnost** -- obsahuje jazyk konečný počet řetezců?
-  * **Náležitost řetezce do jazyka** -- je daný řetezec řetezcem jazyka?
-  * **Inkluze** --je jazyk generovaný jednou gramatikou podmnožinou jazyku generovaného druhou gramtikou?
-  * **Ekvivalence gramatik** -- generují dvě gramatiky stejné jazyky?
-^  Jazyk  ^  Neprázdnost  ^  Prázdnost  ^  Konečnost  ^  Náležitost  ^  Inkluze  ^  Ekvivalence  ^
-^  3  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |  ✔  |
-^  2 (deterministické)  |  ✔  |  ✔  |  ✔  |  ✔  |  ✘  |  ✔  |
-^  2  |  ✔  |  ✔  |  ✔  |  ✔  |  ✘  |  ✘  |
-^  1  |  částečně  |  ✘  |  ✘  |  ✔  |  ✘  |  ✘  |
-^  0 (rekurzivní)  |  částečně  |  ✘  |  ✘  |  ✔  |  ✘  |  ✘  |
-^  0  |  částečně  |  ✘  |  ✘  |  částečně  |  ✘  |  ✘  |
-===== Vlastnosti jazyků =====
-==== Typ 3 – Regulární jazyky ====
-=== Pumping lemma ===
-Nechť //L// je nekonečný regulární jazyk. Pak existuje celočíselná konstanta //p// ≥ 0 taková, že platí:
-//w// ∈ //L// ∧ |//w//| ≥ //p// => //w// = //xyz// ∧ 0 < |//y//| ≤ //p// ∧ //xyⁱz// ∈ //L// (//i// ≥ 0)
-Neformálně: V každé dostatečně dlouhé větě každého regulárního jazyka jsme schopni najít poměrně krátkou sekvenci, kterou je možné vypustit, resp. zopakovat libovolně krát přičemž dostáváme stále věty daného jazyka.
-<note important>Není to podmínka dostačující ale nutná! Nestačí to jako důkaz že jazyk je regulární. Ale dá se tím dokázat že regulární není.</note>
-=== Prefixová ekvivalence ~L ===
-Dva prvky //u//, //v// jsou prefixově ekvivalentí (//u// ~<sub>//L//</sub> //v//) pokud platí:
-∀ //w// ∈ //Σ//<sup>*</sup>: //uw// ∈ //L// <=> //vw// ∈ //L//
-Tj. pokud lze oba řetězce přidat jako prefix jakémukoli řetězci jazyka a vzniklá slova buď obě budou nebo obě nebudou v jazyce //L//
-<note>Index ekvivalence je počet tříd rozkladu podle ekvivalence</note>
-=== Pravá konguruence ===
-Ekvivalence je pravou kongruencí pokud platí, že za dva ekvivalentní prvky lze připojit nějaký symbol abecedy a prvky budou stále ekvivalentní.
-=== Myhill-Nerodova věta ===
-  - Nechť //L// je jazyk nad //Σ//, pak následující tvrzení jsou ekvivalntní:
-    * //L// je jazyk přijímaný deterministickým konečným automatem.
-    * //L// je sjednocení některých tříd rozkladu určeného pravou kongruencí na //Σ//<sup>*</sup> s konečným indexem.
-    * Relace ~<sub>//L//</sub> má konečný index.
-  - Počet stavů libovolného minimálního deterministického konečného automatu přijímajícího //L// je roven indexu ~<sub>//L//</sub> (takový DKA existuje právě tehdy, když ~<sub>//L//</sub> je konečný)
-<note tip>Každý konečný jazyk je regulární (opak neplatí).</note>
-=== Uzavřenost ===
-  * Sjednocení, konkatenace, iterace -- plyne z definice regulárních množin a ekvivalence regulárních množin a regulárních jazyků
-  * Komplement -- KA, množina koncových stavů = Q\F
-  * Průnik -- deMorganovy zákony
-=== Rozhodnutelnost ===
-  * Neprázdnost -- ano -- DKA: //L//(//M//) ≠ ∅ <=> ∃ //q// ∈ //Q//: (//q// ∈ //F// ∧ //q// je dostupný z //q//₀)
-  * Náležitost -- ano -- DKA: //w// ∈ //L// <=> (//q//₀, //w//) ⊢<sup>*</sup> (//q//, //ε//) ∧ //q// ∈ //F//
-  * Ekvivalence -- ano -- pro každý jazyk sestavíme KA, kde množiny //Q//₁ a //Q//₂ neobsahují stejný stav. Sestrojíme KA, kde nové množiny vzniknou sjednocením původních dvou a počateční stav bude počáteční stav prvního automatu. Vypočítáme relaci nerozlišitelnosti stavů z //Q//₁ ∪ //Q//₂. Potom //L//(//G//₁) = //L//(//G//₂) <=> //q//₀¹ ≡ //q//₀²
-==== Typ 2 – Bezkontextové jazyky ====
-=== Pumpig lemma ===
-Pokud je jazyk //L// bezkontextový, existuje číslo //p// > 0 tak, že každé slovo //w// z //L//, pro které platí |//w//| ≥ //p//, lze zapsat ve tvaru
-//w// = //uvxyz//, |//vy//| > 0, |//vxy//| ≤ //p//, a //uvⁱxyⁱz// patří do //L// pro každé //i// ≥ 0.
-Problém, zda daný bezkontextový jazyk je deterministický bezkontextový jazyk, není obecně rozhodnutelný.
-Problém, zda daná gramatika je nebo není víceznačná, je nerozhodnutelný.
-=== Uzavřenost ===
-  * Substituce jazyků
-  * Sjednocení -- plyne ze substituce //Lₘ//, //Lₙ// do jazyka {//m//, //n//}
-  * Konkatenace -- plyne ze substituce //Lₘ//, //Lₙ// do jazyka {//mn//}
-  * Iterace -- plyne ze substituce //Lₘ// do jazyka {//m//}<sup>*</sup>
-  * Pozitivní iterace -- plyne ze substituce //Lₘ// do jazyka {//m//}⁺
-  * Morfismus
-  * Inverzní morfismus
-  * Průnik s regulárními jazyky -- ZA přijímající průnik na konečném řízení, zásobníkové operace zůstavají
-  *
-=== Neuzavřenost ===
-  * Průnik -- jazyky //aᵐbᵐcⁿ// a //aᵐbⁿcⁿ// jsou oba bezkontextové, průnik je jazyk //aⁿbⁿcⁿ//, což není bezkontextový
-  * Doplněk -- deMorganových zákonů a uzavřenosti vůči sjednocení
-=== Rozhodnutelnost ===
-  * Neprázdnost jazyka -- ano -- algoritmus určující množinu neterminálů generujících terminální řetězce
-  * Příslušnost řetězce do jazyka -- ano -- průnik NZA s KA přijímajícím řetězec //w//
-  * Konečnost jazyka -- ano -- Pumping lemma
-  * Ekvivalence jazyků -- ne -- redukce z nerozhodnutelného Postova korespondenčního problému
-  * Inkluze jazyků -- ne -- redukce z nerozhodnutelného Postova korespondenčního problému
-==== Deterministické bezkontextové jazyky ====
-=== Uzavřenost ===
-* průnik s regulárními jazyky
-* doplněk
-==== Neuzavřenost ====
-* průnik - stejně jako BKG
-* sjednocení - stejně jako BKG
-* konkatenace - jazyky <math>a^mb^mc^n</math> a <math>a^mb^nc^n</math> - DZA nemuže odhadnout, zda má kontrolovat první nebo druhou rovnost
-* iterace
-==== Typ 1 - Kontextové jazyky ====
-=== Uzavřenost ===
-* sjednocení
-* průnik
-* konkatenace
-* iterace
-* doplněk
-=== Rozhodnutelnost ===
-* členství věty - ano - rekurzivnost
-* inkluze jazyků - ne
-==== Typ 0 - Rekurzivně vyčíslitelné jazyky ====
-;Riceova věta
-: Každá netriviální vlastnost rekurzivně vyčíslitelných jazyků je nerozhodnutelná.
-: Každá netriviální nemonotónní vlastnost rekurzivně vyčíslitelných jazyků není ani částečně rozhodnutelná.
-* Pozn.: Triviální vlastnost - je vždy pro všechny množiny pravdivá nebo nepravdivá
-* Pozn.: Monotónní vlastnost - pokud monotónní vlastnost platí v podmnožině tak platí i v nadmnožině
-; Jsou-li jazyky <math>\,L</math> i <math>\overline{L}</math> rekurzivně vyčíslitelné jsou oba rekurzivní.
-=== Uzavřenost ===
-* sjednocení
-* průnik
-* konkatenace
-* iterace
-=== Neuzavřenost ===
-* doplněk - nelze požít postup jako u úplného TS, cyklení zůstane
-=== Rozhodnutelnost ===
-* náležitost jazyka - částečně - úplný TS, který bude simulovat TS nad daným řetězcem w
-==== Rekurzivní jazyky ====
-=== Uzavřenost ===
-* doplněk - TS vždy zastaví, při nepřijetí řetězce přejde do stavu REJECT. Doplněk dostaneme záměnou stavu REJECT s původním koncovým stavem.

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku