1.2 Klasifikace formálních jazyků
Regulární jazyky
Regulární jazyky (zkráceně RJ) tvoří nejjednodušší množinu formálních jazyků. Formální jazyk je regulární právě tehdy, když jej lze generovat regulární gramatikou. Pro regulární jazyky dále platí, že je lze:
- přijmout (ne)deterministickým konečným automatem,
- popsat regulárním výrazem.
Bezkontextové jazyky
Bezkontextové jazyky (zkráceně BJ) jsou dalším typem formálních jazyků. Formální jazyk je bezkontextový právě tehdy, když jej lze generovat bezkontextovou gramatikou. Pro bezkontextové jazyky dále platí, že je lze:
- přijmout nedeterministickým zásobníkovým automatem.
Kontextové jazyky
Kontextové jazyky (zkráceně KJ) jsou třetím typem formálních jazyků. Formální jazyk je kontextový právě tehdy, když jej lze generovat kontextovou gramatikou. Pro kontextové jazyky dále platí, že je lze:
- přijmout nedeterministickým lineárně omezeným Turingovým strojem,
- generovat nezkracující gramatikou.
Rekurzivně spočetné jazyky (RSJ)
Rekurzivně spočetné jazyky
Rekurzivně spočetné jazyky (zkráceně RSJ) jsou čtvrtým typem formálních jazyků. Formální jazyk je rekurzivně spočetný právě tehdy, když jej lze generovat neomezenou gramatikou. Pro rekurzivně spočetné jazyky dále platí, že je lze:
- přijmout (ne)deterministickým Turingovým strojem.
Hierarchie jazyků
- Regulární jazyk je vždy zároveň bezkontextový, kontextový a rekurzivně spočetný.
- Bezkontextový jazyk je vždy zároveň kontextový a rekurzivně spočetný.
- Kontextový jazyk je vždy zároveň rekurzivně spočetný.
Formální jazyky obsahují jako podmnožiny jazyky regulární, bezkontextové, kontextové a rekurzivně spočetné. Existují však i jazyky, které do žádné z těchto čtyř množin nespadají. Jedná se o jazyky, které nejsou rozpoznatelné Turingovým strojem.
Uzavřenost jazyků
Uzavřenost jazyků pro vybrané operace
Následující tabulka shrnuje uzavřenost tříd jazyků pro vybrané operace (✓ = uzavřeno, ✗ = neuzavřeno):
Co to pro nás znamená, když je třída jazyků uzavřená pro nějakou operaci?
Provedeme-li se dvěma jazyky operaci, pro níž je jim odpovídající třída jazyků uzavřená, výsledkem bude opět jazyk z této třídy.
Například:
- Regulární jazyky jsou uzavřené pro operaci průnik. Pokud tedy provedeme průnik dvou regulárních jazyků, výsledkem bude opět jazyk regulární. Nikdy se nestane, že by výsledkem byl jazyk neregulární.
- Bezkontextové jazyky jsou uzavřené pro operaci sjednocení. Pokud tedy sjednotíme dva bezkontextové jazyky, výsledkem bude opět jazyk bezkontextový.
- Bezkontextové jazyky nejsou uzavřeny pro operaci průnik. Pokud tedy provedeme průnik dvou bezkontextových jazyků, výsledkem pouze může (ale nemusí) být jazyk bezkontextový.
