Vlastnosti formálních jazyků

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

• 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?

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.

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

Ekvivalence je pravou kongruencí pokud platí, že za dva ekvivalentní prvky lze připojit nějaký symbol abecedy a prvky budou stále ekvivalentní.

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ý)

• 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

• 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₀²

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

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

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

• 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

• Průnik s regulárními jazyky
• Doplněk

• 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

• Sjednocení
• Průnik
• Konkatenace
• Iterace
• Doplněk

• Členství věty – ano – rekurzivnost
• Inkluze jazyků – ne

• 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¹⁾ rekurzivně vyčíslitelné jsou oba rekurzivní.

• Sjednocení
• Průnik
• Konkatenace
• Iterace

• Doplněk – nelze požít postup jako u úplného TS, cyklení zůstane

• Náležitost jazyka – částečně – úplný TS, který bude simulovat TS nad daným řetězcem w

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