17 - Vlastnosti formálních jazyků (typické vlastnosti a jejich rozhodnutelnost) Flashcards
Uzavřenost vůči operacím (základní operace - subtituce, morfismus, inverzní morfismus)
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) - nahrazení + konkatenace
- σ(ab) = σ(a)σ(b) = {0, 00}{1, 111, 1110} -> σ(ab) = {01, 0111, 01110, 001, 00111, 001110}
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) - je to taková jednoduchá subtituce
- ϕ(a) = 00, ϕ(b) = 01 a ϕ(c) = 10 -> ϕ(abac) = ϕ(a)ϕ(b)ϕ(a)ϕ(c) = 00010010
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
Uzavřenost vůči operacím (základní MNOŽINOVÉ operace - sjednocení, průnik, rozdíl, doplněk, kontaktenace, reverzace, iterace))
Sjednocení - jazyk obsahuje řetězce z obou jazyků: L1∪L2 = {x: x∈L1∨x∈L2}
Průnik - jsou přijímány pouze řetězce, které jsou společné pro oba jazyky L1∩L2 = {x: x∈L1∧x∈L2}
Rozdíl - L1−L2 = {x: x∈L1∧x∉L2}
Doplněk - přijímáme všechny řetězce z dané abecedy kromě těch řetězců, které patří do jazyka L: L ̅=Σ^∗−L
Konkatenace - L1L2 = {xy: x∈L1∧y∈L2} - každý s každým (zachovává pořadí)
Reverzace - reverse(L)={reverse(x):x∈L} - 01 -> 10
Iterace - všechny možný kombinace které můžou vznknout (sjednocení iterací)
Uzavřenosti jazyků vůči operacím
Ano -> uzavřenost pro všechny
Typ 3 - Regulární - Ano
Typ 2 - deterministické bezkontextové - Ne pro všechno kromě Doplňku, inv. morfismu a průniku s typ 3
Typ 2 - bezkontextové - Ne - Průnik, doplněk
Typ 1 - kontextové - Ano
Typ 0 - rekurzivní (vždy zastaví) - Ne - Substituce, Morfismus
Typ 0 - rekurzivně vyčíslitelné (může cyklit) - Ne - Doplněk
Rozhodnutelnost problémů v jazycích (problémy)
• 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?
○ U rekurzivně vyčístelného jazyka může TS cyklit pokud tam řetězec nenáleží.
• Inkluze – je jazyk generovaný jednou gramatikou podmnožinou jazyku generovaného druhou gramatikou?
• Ekvivalence gramatik – generují dvě gramatiky stejné jazyky?
Rozhodnutelnost jazyků
Typ 3 - Regulární - Ano - vše
Typ 2 - deterministické bezkontextové - Ne - Inkluze
Typ 2 - bezkontextové - Ne - Inkluze a ekvivalence
Typ 1 - kontextové - částečně - neprázdnost, ANO - náležitost (necyklení), NE zbytek
Typ 0 - rekurzivní (vždy zastaví) - částečně - neprázdnost, ANO - náležitost (necyklení), NE zbytek
Typ 0 - částečně - neprázdnost, náležitost (cyklení), NE zbytek
Vlastnosti konkrétních jazyků - Typ 3 - Regulární jazyky
Pumping lemma - dokážeme že jazyk NENÍ REGULÁRNÍ
- Nechť L je nekonečný regulární jazyk (každý konečný jazyk je totiž regulární). 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.
Prefixová ekvivalence ~L - věty s oběma prefixy vždy patří do jazyka - ∀ w ∈ Σ: uw ∈ L ⇔ vw ∈ L
Dva prvky u, v jsou prefixově ekvivalentí (u ~L v) pokud platí:
∀ w ∈ Σ: uw ∈ L ⇔ vw ∈ L
Pravá kongurence (výsledek pravé konkatenace zachovává vlastnosti - pro každé u,v,w∈Σ∗ platí u∼v⇒uw∼vw)
ekvivalence je pravou kongruencí pokud platí, že za dva ekvivalentní prvky lze připojit nějaký symbol abecedy a prvky budou stále ekvivalentní
- Nechť Σ je abeceda a ∼ je ekvivalence na Σ∗. Ekvivalence ∼ je pravou kongruencí (je zprava invariantní), pokud
pro každé u,v,w∈Σ∗ platí u∼v⇒uw∼vw
Myhill-Nerodova věta
1. 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 Σ* s konečným indexem.
○ Relace ~L má konečný index.
2. Počet stavů libovolného minimálního deterministického konečného automatu přijímajícího L je roven indexu ~L (takový DKA existuje právě tehdy, když ~L je konečný)
Každý konečný jazyk je regulární (opak neplatí).
důkaz ekvivalence - automaty zminimalizuje a porovnám, budou mít stejnou strukturu
• Sjednocení, konkatenace, iterace – plyne z definice regulárních množin a ekvivalence regulárních množin a regulárních jazyků ○ Tyto operace umím dělat s konečnýmy stavovými automaty a vždy mi vyjde konečný automat :-) • Komplement – KA, množina koncových stavů = Q\F ○ Stačí prohodit koncové a nekoncové stavy • Průnik – deMorganovy zákony - komplement
Vlastnosti konkrétních jazyků - Typ 2 - Bezkontextové jazyky
Typ 2 – Bezkontextové jazyky Pumping lemma (můžeme dokázat že daný jazyk není bezkontextový) 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ý.
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
• 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
Vlastnosti konkrétních jazyků - Typ 2 - Deterministické Bezkontextové jazyky
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
Vlastnosti konkrétních jazyků - Typ 1 - Kontextové jazyky
Typ 1 – Kontextové jazyky Uzavřenost - vše • Sjednocení • Průnik • Konkatenace • Iterace • Doplněk Rozhodnutelnost • Členství věty – ano – rekurzivnost • Inkluze jazyků – ne prázdnost jazyka - ne (redukce z Postova problému přiřazení)
Vlastnosti konkrétních jazyků - 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 ¬L1 rekurzivně vyčíslitelné jsou oba rekurzivní.
Neuzavřenost
• Doplněk – nelze použí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.
