Kalábovi

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== 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 ====
=== Pumping 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 //aᵐbᵐcⁿ// a //aᵐbⁿcⁿ// -- 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á.

  * Triviální vlastnost -- je vždy pro všechny množiny pravdivá nebo nepravdivá
  * Monotónní vlastnost -- pokud monotónní vlastnost platí v podmnožině tak platí i v nadmnožině

Jsou-li jazyky //L// i ¬//L//((doplněk)) 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

Nástroje pro stránku
