Chomského hierarchia

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
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

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^nb^n~|~n\geq 0\}
\mathcal{L}_{ECS}-\mathcal{L}_{CF} \{a^nb^nc^n~|~n\geq 0\}
\mathcal{L}_{RE}-\mathcal{L}_{ECS} diagonálny jazyk,univerzálny jazyk
Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.