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

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

Граматика на Чомски

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

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

където

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

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

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

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

$a\rightarrow b$.

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

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

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

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

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

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

$L_{g}=\lbrace w\in T^{*}\ |\ \langle S\rangle \Rightarrow ^{*}w\rbrace$

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

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

$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)$.

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

Примери

Граматика с терминални символи {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 \langle \varepsilon \rangle \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, които съдържат само правила, които са

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

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

Абстрактни машини

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

Граматика	Език	Автомат
Тип 0	рекурсивно изброим	машина на Тюринг
Тип 1	контекстен	линейно ограничена недетерминистична машина на Тюринг
Тип 2	безконтекстен	?автомат? [FIXME pushdown automaton/Kellerautomat]
Тип 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.