Chomského hierarchia

Chomského hierarchia jazykov je porovnanie štyroch tried formálnych jazykov (a tým aj sily ich príslušných gramatík a automatov):

kde

  je trieda regulárnych jazykov,
  je trieda bezkontextových jazykov,
  je trieda rozšírených kontextových jazykov,
  je trieda rekurzívne vyčísliteľných jazykov.

Túto hierarchiu (systém inklúzií) popísal ako prvý americký informatik a lingvista Noam Chomsky v roku 1956.

Nové jazyky, príp. jazyky generované novými gramatikami či akceptované novými automatmi, sa často porovnávajú s týmito jazykmi. Ich zaradením do Chomského hierarchie získame odhad ich sily vzhľadom na známe klasické jazyky (gramatiky, automaty). Niektoré jazyky sa pekne zaraďujú do tejto hierarchie (napr. trieda rekurzívnych jazykov : ), kým iné zasa vôbec (napr. trieda jazykov generovaných 0L systémami ).

Chomského hierarchia jazykov však nepokrýva všetky jazyky, t. j. existujú jazyky, ktoré nie sú ani rekurzívne vyčísliteľné (pozri napr. problém zastavenia).

Všetky jazyky Chomského hierarchie sú generované gramatikami, ktoré vznikli z frázovej gramatiky postupných pridávaním obmedzení na prepisovacie pravidlá. Nasledujúca tabuľka zhŕňa jazyky tejto hierarchie, k nim zodpovedajúce gramatiky a povolené prepisovacie pravidlá a typ automatu, ktorý ich dokáže akceptovať:

 Jazyk Gramatika Prepisovacie pravidlá Automat Rekurzívne vyčísliteľný  Frázová (žiadne obmedzenia)  Turingov stroj Rozšírený kontextový (Rozšírená) kontextová  Nedeterministický lineárne ohraničený automat Bezkontextový Bezkontextová  Nedeterministický zásobníkový automat Regulárny  Regulárna  Konečný automat

(v tabuľke , je počiatočný neterminál a v rozšírených kontextových gramatikách sa  nevyskytuje na pravej strane žiadneho pravidla)

Všetky inklúzie v Chomského hierarchii sú vlastné. Nasledujúca tabuľka uvádza príklady jazykov, ktoré sa nachádzajú v príslušných rozdieloch tried:

 Rozdiel Príklad      diagonálny jazyk,univerzálny jazyk

Kategória:Formálne jazyky
Kategória:Teória automatov
Kategória:Eponymické termíny v informatike