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):

${\mathcal {R}}\subsetneq {\mathcal {L}}_{CF}\subsetneq {\mathcal {L}}_{ECS}\subsetneq {\mathcal {L}}_{RE}$

kde

• ${\mathcal {R}}$ je trieda regulárnych jazykov,
• ${\mathcal {L}}_{CF}$ je trieda bezkontextových jazykov,
• ${\mathcal {L}}_{ECS}$ je trieda rozšírených kontextových jazykov,
• ${\mathcal {L}}_{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 ${\mathcal {L}}_{Rec}$: ${\mathcal {L}}_{ECS}\subsetneq {\mathcal {L}}_{Rec}\subsetneq {\mathcal {L}}_{RE}$), kým iné zasa vôbec (napr. trieda jazykov generovaných 0L systémami ${\mathcal {L}}_{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\rightarrow v,|u|\leq |v|,\sigma \rightarrow \varepsilon$	Nedeterministický lineárne ohraničený automat
Bezkontextový	Bezkontextová	$\xi \rightarrow u$	Nedeterministický zásobníkový automat
Regulárny	Regulárna	$\xi \rightarrow w\alpha ~|~w~|~\varepsilon$	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
${\mathcal {L}}_{CF}-{\mathcal {L}}_{R}$	$\{a^{n}b^{n}~|~n\geq 0\}$
${\mathcal {L}}_{ECS}-{\mathcal {L}}_{CF}$	$\{a^{n}b^{n}c^{n}~|~n\geq 0\}$
${\mathcal {L}}_{RE}-{\mathcal {L}}_{ECS}$	diagonálny jazyk,univerzálny jazyk