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

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

Zdroj: "http://sk.wikipedia.org../../../c/h/o/Chomsk%C3%A9ho_hierarchia.html"

Kategória: Formálne jazyky a automaty

##### Views

- Stránka
- Diskusia
- Aktuálna verzia

##### Hľadaj

##### Iné jazyky

- Afrikaans
- Български
- Català
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- Hrvatski
- Italiano
- 日本語
- 한국어
- Nederlands
- ‪Norsk (nynorsk)‬
- Polski
- Português
- Română
- Русский
- 中文