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

1049 байтове добавени ,  преди 17 години
1ви пара, допълнителни връзки, рег. изрази, ...
м (→‎Тип 1: фмт)
(1ви пара, допълнителни връзки, рег. изрази, ...)
'''Йерархията на Чомски''' е [[йерархия]] от класове [[формална граматика|формални граматики]], образуващи [[формален език|формални езици]]. Въведена е през [[1956]] г. от американския [[лингвистика|лингвист]] [[Ноам Чомски]]. Освен в лингвистиката, моделът на граматиките на Чомски намира широко приложение и в други науки, като [[информатика]]та (тясно свързано със съответствията с концепти от [[Теория на автоматитие|теорията на автоматите]]) и [[биология]]та ([[Нилс К. Йерне]] озаглавява [[Нобелова награда|нобеловата]] си лекция ''Генеративната граматика на имунната система'' и разглежда [[белтък|протеиновия]] строеж в такъв контекст).
 
==Граматика на Чомски==
===Тип 1===
Граматиките от ''тип 1'' ([[контекстна граматика|контекстните граматики]]) са граматики, които съдържат само правила със следния вид
: <math>v \circ a \circ w \rightarrow v \circ \langle b\rangle \circ w;\ v,w \in (T\cup N)^*, a\in (T\cup N)^+, b\in N</math>.
(За множество М, М<sup>+</sup> е съкращение на <math>M^* - \lbrace\langle\varepsilon\rangle\rbrace</math>.)
 
Такива правила се наричат ''контекстни[[контекст]]ни'' (англ. ''context-sensitive'').
 
В граматиките от тип 1 се допуска и правилото
 
===Тип 2===
Граматики от ''тип 2'' ([[безконтекстна граматика|безконтекстните граматики]]) са всички граматики от тип 1, които съдържат само правила от вида
: <math>a \rightarrow \langle b \rangle;\ a\in (T\cup N)^*, b\in N</math>.
се наричат ''терминални''.
Граматики от ''тип 3'' ([[регулявна граматика|регулярни граматики]]) са всички граматики от тип 2, които съдържат само правила, които са
* терминални или ляволинейни; или
* терминални или дяснолинейни
Езиците на тези граматики могат да се опишат и чрез [[регулярен израз|регулярни изрази]].
 
==Абстрактни машини==
* Broy M. 1998. ''Einf&uuml;hrung i.d. Informatik'', Band 2, стр. 191-212. Berlin, Heidelberg: Springer.
[[Категория:Лингвистика]] [[Категория:Формални езици]]
[[de:Chomsky-Hierarchie]]
3280

редакции