V teoretické informatice , teorii jazyků a vypočítatelnosti je Chomského hierarchie (někdy nazývaná Chomsky- Schützenbergerova hierarchie ) klasifikací formálních gramatik (a potažmo příslušných formálních jazyků generovaných gramatikami), kterou popsal Noam Chomsky v roce 1956. .
Hierarchie zavedená Noamem Chomským je založena na formálním gramatickém modelu . Definuje třídy své hierarchie jako možné modely pro popis strukturních vlastností přirozených jazyků. Noam Chomsky navrhl klasifikaci do čtyř typů jazyků, od typu 0 do typu 3. Tato počáteční terminologie byla zachována, ale jiné názvy jsou nyní běžnější. Chomsky představil tyto rodiny z hlediska formálních gramatik a různé třídy gramatik jsou definovány postupnými omezeními ve formě pravidel.
Pozoruhodnou vlastností Chomského klasifikace je to, že pro každý typ existuje rodina automatů, které přijímají přesně jazyky tohoto typu. Tyto řadiče se liší povahou a použitím pomocné paměti. Překlad do tříd složitosti je méně jasný: racionální jazyky (typ 3) jsou v DTIME (n), algebraické jazyky (typ 2) v DTIME (n 3 ), kontextové jazyky (typ 1) v DTIME ( n M ), kde M závisí na gramatice, ale obrácení není pravdivé.
Chomského klasifikace, která se používá téměř ve všech příručkách pro výuku informatiky, se ve svých aplikacích ukázala jako velmi plodná, zejména při navrhování a analýze programovacích jazyků a kompilaci těchto jazyků. Racionální a algebraické jazyky byly v minulosti předmětem rozsáhlých teoretických studií. Tyto kontextové jazyky jsou používány hlavně v popisu přirozených jazyků.
Chomsky definoval čtyři třídy gramatik, pojmenované typ 0 až typ 3, a tedy také čtyři třídy jazyků, generované těmito hierarchicky vnořenými gramatikami:
Všechny jazyky typu 3 jsou jazyky typu 2. Všechny jazyky typu 2 jsou jazyky typu 1. Všechny jazyky typu 1 jsou jazyky typu 0. Následující tabulka shrnuje korespondenci mezi typy gramatiky, jazyky a stroji.
Gramatika | Pravidla výroby | Jazyk | Stroj |
---|---|---|---|
zadejte 0 | rekurzivně spočetné | Turingův stroj | |
typ 1 | kontextové | Lineárně ohraničený automat | |
typ 2 | algebraický | Non-deterministický stack automat | |
typ 3 | Racionální | Hotový automat |
Ve formální prezentaci níže je slovní zásoba gramatiky složená z terminálních a nekoncových znaků , je sada nekoncových znaků a je prázdným slovem.
Pravidla neexistují žádná omezení. Mají formu:
Tyto gramatiky generují třídu rekurzivně vyčíslitelných jazyků . Jedná se přesně o jazyky rozpoznatelné Turingovým strojem . Problém, zda slovo patří do jazyka této třídy, je nerozhodnutelný .
Pravidla mají formu:
Jinými slovy, jakékoli pravidlo obsahuje neterminál obklopený dvěma slovy, která popisují kontext, ve kterém lze proměnnou nahradit. Tyto gramatiky se nazývají kontextové (v angličtině kontextové ), protože nahrazení neterminálního prvku může záviset na prvcích kolem něj: jeho kontextu. Vyráběné jazyky, nazývané kontextové nebo kontextově citlivé jazyky , jsou přesně ty, které rozpoznává nedeterministický Turingův stroj s lineárně ohraničenou pamětí, běžně nazývanou lineárně ohraničené automaty . Jiné ekvivalentní formulace existují pro gramatiky definující kontextové jazyky.
Pravidla mají formu:
Na takové pravidlo lze pohlížet jako na kontextové pravidlo, kde je kontext pravidel prázdný, za předpokladu, že pravým členem není prázdné slovo. Adjektivum „bezkontextový“ vyjadřuje skutečnost, že s nekoncovými symboly se zachází bez ohledu na to, kde se objevují. Tyto gramatiky generují přesně algebraické jazyky , které se také nazývají bezkontextové jazyky, nekontextové jazyky nebo nekontextové jazyky. Rozeznává je automat na baterie .
Pravidelné gramatiky jsou buď levé lineární gramatiky, nebo pravé lineární gramatiky:
Pravidelné gramatiky generují racionální jazyky . Pravidelná gramatika se ve skutečnosti snadno přemění na konečný automat ( Kleeneova věta ).
Pozor, nemůžeme dovolit dva typy pravidel současně v gramatice, aniž bychom opustili třídu racionálních jazyků: získáváme lineární gramatiky, které tvoří mezilehlou třídu mezi typem 2 a typem 3. Pravidla lineární gramatiky jsou ve tvaru:
Viz také příklady na stránce formální gramatiky . Teorie formálních jazyků má mnoho nástrojů k potvrzení nebo zneplatnění typu jazyka (racionální, algebraický atd.). Explicitní konstrukce gramatiky rozpoznávající daný jazyk není vždy snadná.
Chomského původní hierarchie sestávala ze čtyř tříd. Ostatní třídy se často střídají:
Tyto gramatiky strom sousedit definovat rodinu mezi algebraické jazyky a kontextových jazyků. Jsou přijímány palubními automaty napájenými z baterie . Tyto gramatiky jsou součástí gramatik, které umožňují lepší pochopení struktury přirozených jazyků, seskupených pod názvem kontextově citlivý jazyk (en) .
Existují i další upřesnění, která ukazují, že struktura není „lineární“: pokud například porovnáme lineární jazyky a deterministické algebraické jazyky, zjistíme, že tyto rodiny nejsou obsaženy ani v jednom.
Chomského hierarchie se týká pouze oblasti vypočítatelnosti definované paradigmaticky tím, co dokáže Turingův stroj vypočítat . Kromě toho existují další hierarchie jazyků, včetně aritmetické hierarchie .