Основные понятия теории формальных языков и грамматик

Пусть задан алфавит V терминальных символов. Множество всех конечных слов или цепочек в алфавите V обозначим V*.

Формальный язык L над алфавитом V - это подмножество множества V*, то есть L (V) Í V* [ 3 ].

Конструктивное описание формального языка осуществляется с помощью формальных систем, называемых формальными порождающими грамматиками.

Определение. Формальной порождающей грамматикой G называется формальная система, описываемая с помощью четырех формальных объектов

{ V, W, P, S }, где V - словарь терминалов, W - словарь нетерминалов, причем V Ç W = Æ, P - множество правил вида j ® y, где j и y Î (V È W) ,

S - аксиома грамматики.

Определение. Цепочка b называется выводимой из цепочки a, если они представимы в виде:

b = l j d a = l y d

и в грамматике существует правило вида y ® j.

Определение. Цепочка b называется выводимой из a, если существует конечная последовательность цепочек вывода:

a ® x₀ x₀ ® x_1,..., x_k ® b, где цепочка x_i непосредственно выводима из x_i-1 для всех i = 0,1,..., k-1.

Введем обозначение a ® b. Это значит, что b выводима из a

в грамматике G.

Определение. Языком L (G), порождаемым грамматикой G, называется множество всех цепочек, выводимых из аксиомы грамматики.

Определение. Грамматики G1 и G2 эквивалентны тогда и только тогда, когда они порождают один и тот же язык.

Классификация грамматик Холмского

Тип 0 - грамматика произвольного вида без ограничений на правила вывода.

Тип 1 - контекстная грамматика. Контекстная грамматика, правила которой имеют вид:

a A b ® a w b, A Î W*, w Î (V È W)*,

где w - непустая цепочка, a и b - контекст правила (цепочки символов, которые не заменяются и не изменяются при его применении).

Тип 2 - контекстно-свободная грамматика (КСГ), правила которой имеют вид

A ® a, a Î (V È W)*.

Тип 3 - регулярная грамматика, все правила которой имеют вид:

A ® a B

A ® a, a Î V, B Î W.

Определение. Язык, порождаемый грамматикой определенного типа, называют языком такого же типа.

Пример. Определить тип языка, цепочки которого имеют вид

{ a, aaa, aaaaa... a^2n-1.... }.

Решение. Определим объекты грамматики и определим ее правила, позволяющие строить цепочки заданного языка. Ими будут:

V = {a}, W = {S}, P = { S ® a a S, S ® a }.

Из всего следует, что это язык типа 2.

Пример. Определить тип языка булевых функций.

Решение. Грамматику зададим объектами:

G = {V, W, P, S}, V= { a, b, c, &, È, Ø, (,) }, W = {S},

и правилами вида:

1. S ® (S & S) 4. S ® a

2. S ®(S È S) 5. S ® b

3. S ® Ø S 6. S ® c.

Анализ показывает, что это контекстно-свободная грамматика,

и язык, порождаемый ей, есть язык типа 2.

Пример. Определить тип языка, цепочки которого имеют вид

{ a b }.

Решение. Запишем правила, с помощью которых можно вывести цепочки заданного языка. Они имеют вид:

S ® a S b; S ® a b.

Как показывает анализ, заданный формальный язык принадлежит типу 2.