Chomského hierarchia

Chomského hierachia (diagram tried).

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

$ℛ⊊{ℒ}_{CF}⊊{ℒ}_{ECS}⊊{ℒ}_{RE}$

kde

• $ℛ$ je trieda regulárnych jazykov,
• ${ℒ}_{CF}$ je trieda bezkontextových jazykov,
• ${ℒ}_{ECS}$ je trieda rozšírených kontextových jazykov,
• ${ℒ}_{RE}$ 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 ${ℒ}_{Rec}$: ${ℒ}_{ECS}⊊{ℒ}_{Rec}⊊{ℒ}_{RE}$), kým iné zasa vôbec (napr. trieda jazykov generovaných 0L systémami ${ℒ}_{0L}$).

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á	$u\to v,|u|\le |v|,\sigma \to \epsilon$	Nedeterministický lineárne ohraničený automat
Bezkontextový	Bezkontextová	$\xi \to u$	Nedeterministický zásobníkový automat
Regulárny	Regulárna	$\xi \to w\alpha |w|\epsilon$	Konečný automat

(v tabuľke $\xi \in N,u\in (N\cup T{)}^{*}N(N\cup T{)}^{*},v\in (N\cup T{)}^{*},w\in T^{*}$,$\sigma \in N$ je počiatočný neterminál a v rozšírených kontextových gramatikách sa $\sigma$ 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
${ℒ}_{CF}-{ℒ}_R$	$\{a^n{b}^n|n\ge 0\}$
${ℒ}_{ECS}-{ℒ}_{CF}$	$\{a^n{b}^n{c}^n|n\ge 0\}$
${ℒ}_{RE}-{ℒ}_{ECS}$	diagonálny jazyk,univerzálny jazyk