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