Формальні мови та їх завдання

Множина регулярних мов, заданих усіма можливими регулярними виразами в алфавіті X, називається класом регулярних мов над X.

Регулярні операції застосовні до будь-яких мов, а не тільки до регулярних. За означенням, застосування їх до регулярних мов породжує регулярні мови.

Не всі мови є регулярними. Наприклад, "мова вкладених дужок", задана БНФ

<вкл-дуж> ::= ( ) | ( <вкл-дуж> ),

є множиною {(n)n|n>0}, яка не задається жодним скінченним регулярним виразом (доведення можна знайти в [АУ]). Отже, розглянемо інші, потужніші засоби задання мов.

3. Граматики Хомського

Граматикою Хомського називається четвірка G = (X, N, P, S). Тут

X – алфавіт означуваної мови, або множина термінальних символів (терміналів).

N – множина позначень понять мови, тобто нетермінальних символів (нетерміналів).

P – множина правил виведення (продукцій) вигляду v w, де

v  ( X  N )* N ( X  N )* , w  ( X  N )*

тобто правий ланцюжок є довільною послідовністю терміналів і нетерміналів, а лівий містить принаймні один нетермінал.

S – початковий нетермінал із множини N, або позначення головного поняття, яким позначаються слова мови.Нетермінали записуються словами в дужках <> або великими латинськими буквами. Термінали за необхідності часом беруться в апострофи. Як і в мові БНФ, замість продукцій вигляду v w1ww2 і v w1w2 записується продукція v w1[w]w2, а замість продукцій v w1u1w2 і v w1u2w2 – продукція v1 w1(u1|u2)w2 .

Приклад 3. Множину продукцій граматики

G1 =({ a, 1, 2 },

{ A, B, C, D },

{ A  BC, A  BD, A  B, B  a, C  1, D  2 },

A )

можна переписати у вигляді

{ A  B [ C | D ], B  a, C  1, D  2 }.

Як бачимо, продукції граматики дуже схожі на БНФ як за формою, так і за змістом – лише замість знака "::=" вживається " ". Проте в лівій частині їх продукцій може бути не поодинокий нетермінал, а цілий ланцюжок, у якому обов'язково є нетермінал. За рахунок такого узагальнення граматики виявляються більш потужним засобом задання мов, ніж системи БНФ, тобто існують мови, які задаються граматиками, але не задаються БНФ. Тепер опишемо спосіб, у який граматика G = (X, N, P, S) задає мову.

1. На множині слів об'єднаного алфавіту (X N)* означається відношення безпосередньої виводимості, позначене знаком  G (або  , коли відомо, якою саме є G):