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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип 3

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

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

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

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

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

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

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

Беше ли полезна тази статия?

Оцени я!

Среден рейтинг / 5. Брой гласове:

Ако намираш статията за полезна...

Последвай ни в социалните мрежи!

Съжаляваме, че тази статия не ти беше полезна!

Помогни ни да променим това!