Формальные языки и грамматики

Формальный язык представляет собой множество цепочек в некотором конечном алфавите. К формальным языкам можно отнести искусственные языки для общения человека с машиной – языки программирования.

Для задания описания формального языка необходимо, во-первых, указать алфавит, т. е. совокупность объектов, называемых символами (или буквами), каждый из которых можно воспроизводить в неограниченном количестве экземпляров (подобно обычным печатным буквам или цифрам), и, во-вторых, задать формальную грамматику языка, т. е. перечислить правила, по которым из символов строятся их последовательности, принадлежащие определяемому языку, – правильные цепочки [10].

Пусть алфавит символов (непустое конечное множество), из которых строятся цепочки языка L, представляет собой алфавит терминальных символов V_T (например, буквы кириллицы или двоичные символы 0 и 1).

Определение формальной грамматики требует наличие ещё одного алфавита V_N – непустого конечного множества нетерминальных (состоящих из некоторого множества терминальных) символов, таким образом что алфавиты терминальных и нетерминальных символов являются непересекающимися (например, слова русского языка за исключением различного рода предлогов «а», «и» и т. п. или двухразрядные двоичные числа {00,01,11,10}) множествами. Объединение этих алфавитов называется словарем формального языка L.

Продукция языка представляет собой пару α и β, каждый элемент этой пары является цепочкой символов словаря формального языка L:

Продукция обозначается α → β (читается «из α следует β»). Необходимо отметить, что цепочка β является элементом ограниченного использования словаря, поэтому среди продукций не должно быть пар вида α → ε, где ε ­пустая цепочка.

Таким образом, формальная грамматика G – это совокупность четырех объектов:

G = (V_T, V_N, P, S)

где

V_T – алфавит терминальных символов

V_N – алфавит нетерминальных символов

P – конечное множество продукций формальной грамматики G, являющееся подмножеством множества П

S – начальный символ грамматики