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

277 байтове добавени ,  преди 17 години
връзка към линг.; по-добър епсилон в латех, преместване на 1 параграф; алтернатива на тип1 с epsilon-редукция
м (без препратки, имащи само косвена връзка със статията)
(връзка към линг.; по-добър епсилон в латех, преместване на 1 параграф; алтернатива на тип1 с epsilon-редукция)
'''Йерархията на Чомски''' е [[йерархия]] от класове [[формална граматика|формални граматики]], образуващи [[формален език|формални езици]]. Въведена е през [[1956]] г. от американския [[лингвистика|лингвист]] [[Ноам Чомски]].
 
==Граматика на Чомски==
Граматика с терминални символи {''a'', ''b''}, нетерминални символи {S, A, B}, правила:
: <math>S \rightarrow ABS</math>
: <math>S \rightarrow \epsilonvarepsilon</math> (където &epsilon; обозначава празната дума)
: <math>BA \rightarrow AB</math>
: <math>BS \rightarrow b</math>
Терминални символи {''a'', ''b''}, нетерминални {''S''}, аксиома ''S'', правила:
: <math>S \rightarrow aSb</math>
: <math>S \rightarrow \epsilonvarepsilon</math>.
 
==Класове в йерархията==
Граматиките от ''тип 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\epsilonvarepsilon\rangle\rbrace</math>.)
 
Такива правила се наричат ''контекстни'' (англ. ''context-sensitive'').
 
В граматиките от тип 1 се допуска и правилото
(За множество М, М<sup>+</sup> е съкращение на <math>M^* - \lbrace\langle\epsilon\rangle\rbrace</math>.)
: <math>\varepsilon \rightarrow \langle;S\rangle;</math>
стига аксиомата ''S'' да не се среща от лявата страна на нито едно от правилата.
 
===Тип 2===
Граматики от ''тип 2'' (безконтекстните граматики) са всички граматики от тип 1, които съдържат само правила от вида
3280

редакции