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

от Уикипедия, свободната енциклопедия

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

Съдържание

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

Една граматика на Чомски 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 е обратната на → релация), за която важи

Lg(G') = Lr(G).

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

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

Граматика с терминални символи {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.

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

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

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

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

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

Граматиките от тип 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

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

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

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

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

Безконтекстни правила от вида

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, които съдържат само правила, които са

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

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

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

Йерархията на граматиките определя и съответни типове формални езици. Ако за един език 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.

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

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

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

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

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

  • 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.