Йерархия на Чомски

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Йерархията на Чомски е йерархия от класове формални граматики, образуващи формални езици. Въведена е през 1956 г. от американския лингвист Ноам Чомски.

Освен в лингвистиката, моделът на граматиките на Чомски намира широко приложение и в други науки, като информатиката (тясно свързано със съответствията с концепции от теорията на автоматите) и биологията (Нилс К. Йерне озаглавява нобеловата си лекция „Генеративната граматика на имунната система“ и разглежда протеиновия строеж в такъв контекст).

Граматика на Чомски[редактиране | edit source]

Една граматика на Чомски G има следния вид:

G = (T, N, \rightarrow, S)

където

  • T е множество от терминални символи
  • N е множество от нетерминални символи
  • е крайно множество от правила за заместване
  • S е елемент от N, наречен стартов символ или аксиома.

Едно правило за заместване е двойка думи (низове) от символи в TN:

(a, b) \in (T\cup N)^* \times (T\cup N)^*

(т.е. думите са от свободната полугрупа с пораждащо множество TN) и може да се запише като

a \rightarrow b.

Всяко множество → от такива правила представлява релация върху TN*. Ако ab е правило за заместване, а v и w са думи от (T∪N)*, двойката

(v \circ a \circ w, v \circ b \circ w) \in (T\cup N)^* \times (T\cup N)^* (където \circ обозначава конкатенацията)

се нарича приложение на правилото ab и може да се запише като

v \circ a \circ w \Rightarrow v \circ b \circ w

Релацията → (т.е. множеството от правилата) чрез приложението индуцира релация ⇒ върху TN*, която се нарича полугрупова (или алгебрична) обвивка. Рефлексивната транзитивна обвивка на ⇒ обозначаваме с ⇒*.

Една граматика на Чомски дефинира генеративно формален език Lg:

L_g = \lbrace w \in T^*\ |\ \langle S\rangle \Rightarrow^* w\rbrace

Елементи на този език са само думи, състоящи се от терминални символи, които могат да се произведат чрез приложение на правилата, започвайки от думата, съдържаща единствено аксиомата S.

Освен това, всяка граматика на Чомски дефинира редуктивно формален език Lr:

L_r = \lbrace w \in T^*\ |\ w \Rightarrow^* \langle S\rangle\rbrace

Този език включва всички думи, които могат да се редуцират до думата, съдържаща единствено аксиомата S, чрез приложение на правилата.

За да се укаже изрично посоката на приложение, често се говори за редуктивни и генеративни граматики. За всяка редуктивна граматика

G = (T, N, \rightarrow, S)

съществува съответна генеративна граматика

G' = (T, N, \rightarrow^T, S)

(където →T е обратната на → релация), за която важи

L_g(G') = L_r(G).

С други думи, редуктивните и генеративните граматики са взаимно дуални.

Примери[редактиране | edit source]

Граматика с терминални символи {a, b}, нетерминални символи {S, A, B}, правила:

S \rightarrow  ABS
S \rightarrow \varepsilon (където ε обозначава празната дума)
BA \rightarrow AB
BS \rightarrow b
Bb \rightarrow bb
Ab \rightarrow ab
Aa \rightarrow aa

и аксиома S, дефинира генеративно езика на всички думи от вида

a^n \circ b^n

(т.е. n пъти а, последвани от m пъти b).

Следната по-проста граматика дефинира генеративно същия език: Терминални символи {a, b}, нетерминални {S}, аксиома S, правила:

S \rightarrow aSb
S \rightarrow \varepsilon.

Типове в йерархията[редактиране | edit source]

Граматиките на Чомски се класифицират по следния начин. (Дефинициите се ограничават до редуктивния случай, тъй като генеративният е напълно аналогичен.)

Тип 0[редактиране | edit source]

Тип 0 включва всички формални граматики. Дефинираните чрез тях езици са точно тези, които могат да бъдат разпознати от една машина на Тюринг. Тези езици се наричат също рекурсивно изброими езици.

Тип 1[редактиране | edit source]

Граматиките от тип 1 (контекстните граматики) са граматики, които съдържат само правила със следния вид

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.

(За множество М, М+ е съкращение на M^* - \lbrace\varepsilon\rbrace.)

Такива правила се наричат контекстни (англ. context-sensitive).

Граматиките от тип 1 са монотонни спрямо дължината на думата. В тях се допуска и правилото

\varepsilon \rightarrow \langle S\rangle,

ако аксиомата S не се среща от лявата страна на нито едно от правилата.

Тип 2[редактиране | edit source]

Граматики от тип 2 (безконтекстните граматики) са всички граматики от тип 1, които съдържат само правила от вида

a \rightarrow \langle b \rangle;\ a\in (T\cup N)^*, b\in N.

Такива правила се наричат безконтекстни (англ. context-free).

Тип 3[редактиране | edit source]

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Безконтекстни правила от вида
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
v \circ \langle a \rangle \circ w \rightarrow \langle b\rangle;\ v,w\in T^+; a,b\in N

се наричат двустранно линейни. Ако v или w се равнява на празната дума, правилата се наричат съответно ляволинейни или дяснолинейни.

Правила от вида

w \rightarrow \langle b\rangle;\ w\in T^+, b\in N

се наричат терминални.

Граматики от тип 3 (регулярни граматики) са всички граматики от тип 2, които съдържат само правила, които са

  • терминални или ляволинейни; или
  • терминални или дяснолинейни

Езиците на тези граматики могат да се опишат и чрез регулярни изрази.

Йерархия на формалните езици[редактиране | edit source]

Йерархията на граматиките определя и съответни типове формални езици. Ако за един език L съществува граматика G от тип i с L=L(G), то за този език се казва че е от тип i и се записва:

L \in \mathcal{L}_i.

Освен това важи:

\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset \mathcal{L}_0.

Т.е. всички регулярни езици са безконтекстни, всички безконтекстни езици са контекстни и всички контекстни езици са рекурсивно изброими, като нито един от типовете не е равен на друг.

Абстрактни машини[редактиране | edit source]

Типовете в йерархията съответстват на езиците, разпознавани от различни видове абстрактни машини:

Граматика Език Автомат
Тип 0 рекурсивно изброим машина на Тюринг
Тип 1 контекстен линейно ограничена недетерминистична машина на Тюринг
Тип 2 безконтекстен магазинен автомат
Тип 3 регулярен краен автомат

Литература[редактиране | edit source]

  • 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ührung i.d. Informatik, Band 2, стр. 191-212. Berlin, Heidelberg: Springer.