Chomského hierarchia

Z Wikipédie

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 $σ$ 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

Kategória: Formálne jazyky a automaty

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Chomského hierarchia

Z Wikipédie

Views

Navigácia

Hľadať

V iných jazykoch