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.

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í.

Prefixová ekvivalence ~L

Dva prvky u, v jsou prefixově ekvivalentí (u ~L v) pokud platí:

∀ w ∈ Σ*: 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

Index ekvivalence je počet tříd rozkladu podle ekvivalence

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 Σ* s konečným indexem.

Relace ~L 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 ~L (takový DKA existuje právě tehdy, když ~L je konečný)

Každý konečný jazyk je regulární (opak neplatí).

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) ⊢* (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}*

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 <math>a^mb^mc^n</math> a <math>a^mb^nc^n</math> jsou oba bezkontextové, průnik je jazyk <math>a^nb^nc^n</math>, 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.