Йерархия на Чомски: Разлика между версии

м
редакция без резюме
м (Робот Изтриване: fa:وراثت چامسكى)
мРедакция без резюме
'''Йерархията на Чомски''' е [[йерархия]] от класове [[формална граматика|формални граматики]], образуващи [[формален език|формални езици]]. Въведена е през [[1956]] г. от американския лингвист [[Ноам Чомски]]. Освен в [[лингвистика]]та, моделът на граматиките на Чомски намира широко приложение и в други науки, като [[информатика]]та (тясно свързано със съответствията с концепти от [[Теория на автоматите|теорията на автоматите]]) и [[биология]]та ([[Нилс К. Йерне]] озаглавява [[Нобелова награда|нобеловата]] си лекция ''„Генеративната граматика на имунната система“'' и разглежда [[белтък|протеиновия]] строеж в такъв контекст).
 
Освен в [[лингвистика]]та, моделът на граматиките на Чомски намира широко приложение и в други науки, като [[информатика]]та (тясно свързано със съответствията с концепти от [[Теория на автоматите|теорията на автоматите]]) и [[биология]]та ([[Нилс К. Йерне]] озаглавява [[Нобелова награда|нобеловата]] си лекция ''„Генеративната граматика на имунната система“'' и разглежда [[белтък|протеиновия]] строеж в такъв контекст).
 
==Граматика на Чомски==
С други думи, редуктивните и генеративните граматики са взаимно дуални.
===Примери===
===Примери===
Граматика с терминални символи {''a'', ''b''}, нетерминални символи {S, A, B}, правила:
: <math>S \rightarrow ABS</math>
 
==Типове в йерархията==
 
Граматиките на Чомски се класифицират по следния начин. (Дефинициите се ограничават до редуктивния случай, тъй като генеративният е напълно аналогичен.)
: <math>\varepsilon \rightarrow \langle S\rangle</math>,
ако аксиомата ''S'' не се среща от лявата страна на нито едно от правилата.
 
 
===Тип 2===
===Тип 3===
Безконтекстни правила от вида
Безконтекстни правила от вида
: <math>v \circ \langle a \rangle \circ w \rightarrow \langle b\rangle;\ v,w\in T^+; a,b\in N</math>
Т.е. всички регулярни езици са безконтекстни, всички безконтекстни езици са контекстни и всички контекстни езици са рекурсивно изброими, като нито един от типовете не е равен на друг.
 
==Абстрактни машини==
==Абстрактни машини==
Типовете в йерархията съответстват на езиците, разпознавани от различни видове [[абстрактна машина|абстрактни машини]]:
{| rules="all" style="border: thin solid black;"
* Broy M. 1998. ''Einf&uuml;hrung i.d. Informatik'', Band 2, стр. 191-212. Berlin, Heidelberg: Springer.
[[Категория:Лингвистика]] [[Категория:Формални езици]] [[Категория:Теоретична информатика]] [[Категория:Изкуствен интелект]]
[[Категория:Теоретична информатика]]
[[Категория:Изкуствен интелект]]
 
[[af:Chomsky-hiërargie]]