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

м
интервал; козметични промени
м (whitespaces)
м (интервал; козметични промени)
'''Йерархията на Чомски''' е [[йерархия]] от класове [[формална граматика|формални граматики]], образуващи [[формален език|формални езици]]. Въведена е през [[1956]] г. от американския лингвист [[Ноам Чомски]].
 
Освен в [[лингвистика]]та, моделът на граматиките на Чомски намира широко приложение и в други науки, като [[информатика]]та (тясно свързано със съответствията с концепции от [[Теория на автоматите|теорията на автоматите]]) и [[биология]]та ([[Нилс К. Йерне]] озаглавява [[Нобелова награда|нобеловата]] си лекция ''„Генеративната граматика на имунната система“'' и разглежда [[белтък|протеиновия]] строеж в такъв контекст).
 
== Граматика на Чомски ==
Една '''граматика на Чомски''' ''G'' има следния вид:
:<math>G = (T, N, \rightarrow, S)</math>
където
* ''T'' е [[множество]] от ''терминални'' символи
* ''N'' е множество от ''нетерминални'' символи
* ''&rarr;'' е крайно множество от ''правила'' за заместване
* ''S'' е елемент от ''N'', наречен стартов символ или ''аксиома''.
Едно правило за заместване е двойка думи (низове) от символи в ''T''&cup;''N'':
:<math>(a, b) \in (T\cup N)^* \times (T\cup N)^*</math>
(т.е. думите са от свободната [[полугрупа]] с пораждащо множество ''T''&cup;''N'') и може да се запише като
:<math>a \rightarrow b</math>.
Всяко множество &rarr; от такива правила представлява [[релация]] върху ''T''&cup;''N''*. Ако ''a''&rarr;''b'' е правило за заместване, а ''v'' и ''w'' са думи от (T&cup;NT∪N)*, двойката
:<math>(v \circ a \circ w, v \circ b \circ w) \in (T\cup N)^* \times (T\cup N)^*</math> (където <math>\circ</math> обозначава [[конкатенация]]та)
се нарича ''приложение'' на правилото ''a''&rarr;''b'' и може да се запише като
:<math>v \circ a \circ w \Rightarrow v \circ b \circ w</math>
Релацията &rarr; (т.е. множеството от правилата) чрез приложението индуцира релация &rArr; върху ''T''&cup;''N''*, която се нарича ''полугрупова'' (или ''алгебрична'') ''обвивка''. [[рефлексивност|Рефлексивната]] [[транзитивност|транзитивна]] обвивка на &rArr; обозначаваме с &rArr;*.
Една граматика на Чомски дефинира ''генеративно'' формален език L<sub>g</sub>:
:<math>L_g = \lbrace w \in T^*\ |\ \langle S\rangle \Rightarrow^* w\rbrace</math>
Елементи на този език са само думи, състоящи се от терминални символи, които могат да се произведат чрез приложение на правилата, започвайки от думата, съдържаща единствено аксиомата ''S''.
Освен това, всяка граматика на Чомски дефинира ''редуктивно'' формален език L<sub>r</sub>:
:<math>L_r = \lbrace w \in T^*\ |\ w \Rightarrow^* \langle S\rangle\rbrace</math>
Този език включва всички думи, които могат да се редуцират до думата, съдържаща единствено аксиомата ''S'', чрез приложение на правилата.
За да се укаже изрично посоката на приложение, често се говори за ''редуктивни'' и ''генеративни граматики''. За всяка редуктивна граматика
:<math>G = (T, N, \rightarrow, S)</math>
съществува съответна генеративна граматика
:<math>G' = (T, N, \rightarrow^T, S)</math>
(където &rarr;<sup>T</sup> е обратната на &rarr; релация), за която важи
:<math>L_g(G') = L_r(G)</math>.
С други думи, редуктивните и генеративните граматики са взаимно дуални.
=== Примери ===
===Примери===
Граматика с терминални символи {''a'', ''b''}, нетерминални символи {S, A, B}, правила:
: <math>S \rightarrow ABS</math>
: <math>S \rightarrow \varepsilon</math> (където &epsilon;ε обозначава празната дума)
: <math>BA \rightarrow AB</math>
: <math>BS \rightarrow b</math>
: <math>a^n \circ b^n</math>
(т.е. ''n'' пъти ''а'', последвани от ''n'' пъти ''b'').
Следната по-проста граматика дефинира генеративно същия език:
Терминални символи {''a'', ''b''}, нетерминални {''S''}, аксиома ''S'', правила:
: <math>S \rightarrow \varepsilon</math>.
 
== Типове в йерархията ==
Граматиките на Чомски се класифицират по следния начин. (Дефинициите се ограничават до редуктивния случай, тъй като генеративният е напълно аналогичен.)
=== Тип 0 ===
''Тип 0'' включва всички формални граматики. Дефинираните чрез тях езици са точно тези, които могат да бъдат разпознати от една [[машина на Тюринг]]. Тези езици се наричат също ''рекурсивно изброими езици''.
=== Тип 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>.
ако аксиомата ''S'' не се среща от лявата страна на нито едно от правилата.
 
=== Тип 2 ===
Граматики от ''тип 2'' ([[безконтекстна граматика|безконтекстните граматики]]) са всички граматики от тип 1, които съдържат само правила от вида
: <math>a \rightarrow \langle b \rangle;\ a\in (T\cup N)^*, b\in N</math>.
Такива правила се наричат ''безконтекстни'' (англ. ''context-free'').
=== Тип 3 ===
Безконтекстни правила от вида
: <math>v \circ \langle a \rangle \circ w \rightarrow \langle b\rangle;\ v,w\in T^+; a,b\in N</math>
се наричат ''двустранно линейни''. Ако ''v'' или ''w'' се равнява на празната дума, правилата се наричат съответно ''ляволинейни'' или ''дяснолинейни''.
Правила от вида
: <math>w \rightarrow \langle b\rangle;\ w\in T^+, b\in N</math>
се наричат ''терминални''.
Граматики от ''тип 3'' ([[регулярна граматика|регулярни граматики]]) са всички граматики от тип 2, които съдържат само правила, които са
* терминални или ляволинейни; или
* терминални или дяснолинейни
Езиците на тези граматики могат да се опишат и чрез [[регулярен израз|регулярни изрази]].
 
=== Йерархия на формалните езици ===
Йерархията на граматиките определя и съответни типове формални езици. Ако за един език ''L'' съществува граматика ''G'' от тип ''i'' с ''L=L(G)'', то за този език се казва че е от тип ''i'' и се записва:
 
Т.е. всички регулярни езици са безконтекстни, всички безконтекстни езици са контекстни и всички контекстни езици са рекурсивно изброими, като нито един от типовете не е равен на друг.
 
== Абстрактни машини ==
==Абстрактни машини==
Типовете в йерархията съответстват на езиците, разпознавани от различни видове [[абстрактна машина|абстрактни машини]]:
{| rules="all" style="border: thin solid black;"
|}
 
== Литература ==
* Chomsky N. 1956. Three models for the description of language, ''IRE Transactions on Information Theory'', Vol. 2, стр. 113-124.
* Chomsky N. 1959. On certain formal properties of grammars, ''Information and Control'', Vol. 1, стр. 91-112.
* Broy M. 1998. ''Einf&uuml;hrungEinführung i.d. Informatik'', Band 2, стр. 191-212. Berlin, Heidelberg: Springer.
 
[[Категория:Формални езици]]
[[Категория:Теоретична информатика]]