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

* 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 <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

* sjednocení * průnik * konkatenace * iterace * doplněk

* členství věty - ano - rekurzivnost * inkluze jazyků - ne

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

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