|
Во [[компјутерски науки|компјутерските науки]], особено во делот на [[програмски јазици]], '''Хиерархијата на Чомски''' (често пати наркувананарекувана и како '''Чомски - Шуценбергерова хиерархија''') е хиерархиска класа на [[формална граматика|формални граматики]] кои генерираат [[формален јазик|формални јазици]].
Оваа хиерархија на граматики била опишана од страна на [[Ноам Чомски]] во 1956 година (види [[#References|<nowiki>[1]</nowiki>]]). Оваа хиерархија исто така е именувана и по [[Марцел-Пол Шуценбергер]] кој имал главна улога во развојот на теоријата на [[формален јазик|формални јазици]].
== Формални граматики ==
{{main|FormalФормална grammarграматика}}
Формалната граматика се состои од :
* ''почетен симбол''.
Формалната граматика го дефинира (или ''генерира'') ''формалниот јазик'', кој е (најверојатно бесконечно) множество на низи од симболи кои мпжатможат да бидат конструирани со примена на правилата врз низите од симболи кои на почетокот се состојат само од еден пчетенпочетен симбол. Правило може да се примени на низа од симболи по пат на замена на секое појавување на симболите на левата страна од правилото со оние кои се појавуваат на десната страна. Низата на применети правила е наречена ''деривација''. Вакваа граматика дефинира формален јазик на сите зборови кои може да се добијат со деривација од почетниот симбол.
Нетерминалните симболи вообичаено се претставуваат со големи букви, терминалните симболи со мали букви, а почетниот симбол со буквата <math>S</math>. Пример, граматиката со терминални симболи <math>\{a, b\}</math>, нетерминални симболи <math>\{S, A, B\}</math>, и правила:
и почетен симбол <math>S</math>, го дефинира јазикот на сите зборови во форма на <math> a^n b^n </math> (т.е. <math>n</math> копија на <math>a</math> проследено со <math>n</math> копија на <math>b</math>).
Во следниов пример е дадена поедноставна граматика која дефинира сличен јазик:
Терминални симболи <math>\{p, q\}</math>, Нетерминалнинетерминални симболи <math>\{S\}</math>, Почетенпочетен симбол <math>S</math>, правила
: <math>S</math> <math>\rightarrow \,</math> <math>pSq</math>
: <math>S</math> <math>\rightarrow \,</math> ε
Хиерархијата на Чомски се состои од следниве нивоа:
* Тип-0 граматики ([[нерестриктирана граматика|нерестриктирани граматики]]) ги вклучуваат сите формални граматики. Тие ги генерираат сотесите јазици кои можат да бидат препознаени од [[Тјуригова машина|Тјуринговата машина]]. Овие јазици исто така се познати и како [[recursively enumerable language]]. Да напоменеме дека овие јазици се различни од [[рекурзивни јазици|рекурзивните јазици]] кои можат да бидат ''одлучени'' од страна на [[машини кои секогаш завршуваат|секогаш завршните Тјурингови машини]]
* Тип-1 граматики ([[контексно осетлива граматика|контексно осетливи граматики]]) генерираат [[контексно осетлив јазик|контексно остеливиосетливи јазици]]. Овие граматики имаат правила во следнава форма <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> со <math>A</math> нетерминален симбол и <math>\alpha</math>, <math>\beta</math> и <math>\gamma</math> стрингови на терминални и нетерминални симболи. Стринговите <math>\alpha</math> и <math>\beta</math> може да бидат празни, но стрингот <math>\gamma</math> не смее да биде празен. ПравилотПравилото <math>S \rightarrow \epsilon</math> е допуштено ако <math>S</math> не се појавува на десната страна од било кое правило. Јазиците опишани со овие граматики се точно оние јазици кои можат да бидат препознаени од страна на [[линеарно ограничен автомат]] (недетерменистичка Тјурингова машина чија лента е ограничена на константен број од должината на влезот).
* Тип-2 граматики ([[контексно слободна граматика|контексно слободни граматики]]) генерираат [[контексно слободен јазик|контексно слободни јазици]]. TheseОвие areграматики definedсе byдефинирани rulesсо ofправила theво formформа <math>A \rightarrow \gamma</math> withсо <math>A</math> aкако nonterminalнетерминален andсимбол и <math>\gamma</math> aкако stringстринг ofна terminalsтерминали andи nonterminalsнетерминали. TheseОвие languagesјазици areсе exactlyоние allјазици languagesкои thatможат canда beбидат recognizedпрепознаени byод a nonне-deterministicдетерминистички [[pushdown automatonавтомат]]и. ContextКонтексно freeслободните languagesјазици areтеоретски theсе theoreticalоснова basisна forсинтаксата theна syntax of mostповеќето [[programmingпрограмски јазик|програмски languageјазици]]s.
* Тип-3 граматики ([[регуларна граматика|регуларни граматики]]) генерираат [[регуларен јазик|регуларни јазици]]. Овие Suchграматики aги grammarограничуваат restrictsсвоите itsправила rulesна toеден aнетерминален singleсимбол nonterminalна onлевата theстрана left-handи sideеден andтерминален aсимбол right-handна sideдесната consistingстрана, ofсо aможност singleда terminal,му possiblyследи followed (orили precededпретходи, butно notне bothи inдвете theодеднаш sameво grammarиста граматика) byсо aеден singleнетерминален nonterminalсимбол. The ruleПравилото <math>S \rightarrow \epsilon</math> isтука alsoе hereдопуштено allowed ifако <math>S</math> doesне notсе appearпојавува onна theдеснат rightастрана sideод ofбило anyкое ruleправило. Овие Theseјазици languagesсе areоние exactlyјазици allкои languagesможат thatда canбидат beодлучени decidedод byстрана aна [[finiteконечен stateавтомат|конечни automatonавтомати]]. AdditionallyУште повеќе, thisоваа familyфамилија ofна formalформални languagesјазици canможе beда obtainedбиде byдобиена и со [[regularрегуларни expressionsизрази]]. RegularРегуларните јазици languagesвообичаено areсе commonlyкористат usedза toдефинирање defineна searchстрингви patternsза andпребарување theво lexicalлексичката structureструктура ofна programmingпрограмските languagesјазици.
Да напоменеме дека множеството од граматики кои соодветствуваат на рекурзивните јазици не е член на оваа хиерархија.
Note that the set of grammars corresponding to recursive languages is not a member of this hierarchy.
Секој регуларен јазик е контексно слободен, секој контексно слободен јазик е контексно осетлив и секој контексно осетлив јазик е рекурзивен а секој рекурзивен јазик е рекурзивно преброив. Ова се вистински подмножества, што значи дека постојат рекурзивно преброиви јазици кои не се рекурзивни, рекурзивни јазици кои не се контексно осетливи, контексно осетливи јазици кои не се контексно слободни и контексно слободни јазици кои се не регуларни.
Every regular language is context-free, every context-free language is context-sensitive and every context-sensitive language is recursive and every recursive language is recursively enumerable. These are all proper inclusions, meaning that there exist recursively enumerable languages which are not recursive, recursive languages that are not context-sensitive, context-sensitive languages which are not context-free and context-free languages which are not regular.
Следната табела е сумарен приказ на секој од четирите типа на граматики на Чомски, класата на јазик кој го генерира, типот на автомат кој го препознава, и формата на неговите правила.
The following table summarizes each of Chomsky's four types of grammars, the class of language it generates, the type of automaton that recognizes it, and the form its rules must have.
{| class="wikitable"
|-
! Граматика
! Grammar
! Јазици
! Languages
! Автомат
! Automaton
! Правила
! Production rules
|-
| TypeТип-0
| [[рекурзивно преброив јазик|рекурзивно преброиви]]
| [[recursively enumerable language|Recursively enumerable]]
| [[Тјурингова машина]]
| [[Turing machine]]
| <math>\alpha \rightarrow \beta</math> (no restrictions)
|-
| TypeТип-1
| [[контексно осетлива граматика|контексно осетлива]]
| [[context-sensitive grammar|Context-sensitive]]
| [[линеарно ограничен автомат|Линеарно ограничена не детерминистичка Тјурингова машина]]
| [[Linear bounded automaton | Linear-bounded non-deterministic Turing machine]]
| <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>
|-
| TypeТип-2
| [[контексно слободна граматика|контексно слободна]]
| [[context-free grammar|Context-free]]
| Non-deterministicНе детерминистички [[pushdown automatonавтомат]]
| <math>A \rightarrow \gamma</math>
|-
| TypeТип-3
| [[регуларна граматика|регуларна]]
| [[regular grammar|Regular]]
| [[Конечен автомат]]
| [[Finite state automaton]]
| <math>A \rightarrow a</math> and<br /><math>A \rightarrow aB</math>
|}
==Референци==
==References==
*{{cite journal
| last = ChomskyЧомски
| first = NoamНоам
| year = 1956
| title = ThreeТри modelsмодели forза theопис descriptionна of languageјазикот
| journal = IRE TransactionsТрансакции onи InformationИнформациона TheoryТеорија
| issue = 2
| pages = 113-124
}}
*{{cite journal
| last = ChomskyЧомски
| first = NoamНоам
| year = 1959
| title = On certain formal properties of grammars
| journal = InformationИнформација andи ControlКонтрола
| issue = 2
| pages = 137-167
}}
*{{cite book
| last = ChomskyЧомски
| first = NoamНоам
| coauthors = SchützenbergerШуценбергер, MarcelМарсел PП.
| editor = BraffortБрафорт, PП.; HirschbergХиршберг, DД.
| others =
| title = Компјутерско програмирање и Формални јазици
| title = Computer Programming and Formal Languages
| year = 1963
| month =
| publisher = North Holland
| location = AmsterdamАмстердам
| id =
| pages = 118-161
| 