Тема 4.1. Формальные языки и операции над ними

Основные определения и обозначения

Грамматика – это математическая система, определяющая язык.

В грамматике для определения языка используются следующие математические объекты:

Ɲ - конечное множество (алфавит) нетерминальных символов или нетерминалов;

- конечное множество (алфавит) терминальных символов или терминалов, причем Ɲ= ;

- конечное множество правил, называемых продукциями, образования цепочек, которые описывают процесс порождения цепочек языка;

Ɲ - выделенный из Ɲ символ, называемый начальным (или исходным). Вывод любой цепочки языка осуществляется из начального символа.

Из терминальных символов образуются цепочки определяемого языка. Нетерминальные символы используются как промежуточные в процессе порождения (вывода) цепочек языка.

Продукция – это пара цепочек , точнее, элемент множества

Ɲ Ɲ Ɲ Ɲ ,

т.е. элемент декартова произведения множеств Ɲ Ɲ Ɲ и Ɲ . Иначе говоря, первой компонентой продукции является любая цепочка, содержащая хотя бы один нетерминал, а второй компонентой – любая цепочка.

Продукция записывается в виде , где направление стрелки показывает, что при использовании данной продукции в процессе вывода цепочка (или подцепочка) заменяется на цепочку (или подцепочку) . Наличие любой продукции в множестве не предписывает обязательно эту продукцию использовать, а лишь определяет возможность ее использования, если текущая цепочка совпадает с или содержит в себе как подцепочку.

Для обозначения продукций с одинаковой левой частью, т.е. продукций вида: , , , ; используется сокращенная запись .

Шаг вывода цепочки – это однократное использование какой-либо продукции. Шаг вывода, состоящий в замене цепочки (или подцепочки) на цепочку (или подцепочку) , обозначается .

Для обозначения последовательности шагов вывода, например, используется сокращенная запись .

Грамматикой называется четверка Ɲ, , составляющие элементы которой определены выше.

Грамматика определяет язык рекурсивно. Рекурсивность проявляется в задании особого рода цепочек, называемых выводимыми цепочками грамматики Ɲ, :

1) - выводимая в цепочка.

2) Если - выводима в цепочка и содержится в , то - тоже выводимая в цепочка, причем цепочка называется непосредственно выводимой из .

Если - выводимая цепочка, то существует последовательность шагов вывода, позволяющая из начального символа грамматики вывести эту цепочку. Опуская отдельные шаги вывода, вся такая последовательность шагов обозначается как . Т.о., символ обозначает транзитивное замыкание шагов вывода.

Для указания на грамматику , в рамках которой сделан данный шаг вывода, используется обозначение . Символ можно рассматривать как символ отношения “непосредственно выводима в грамматике ”, определенного на множестве всех возможных цепочек алфавита. Транзитивное замыкание отношения обозначается и читается “выводима нетривиальным образом в грамматике ”.

Выводимая цепочка грамматики , не содержащая нетерминальных символов, называется терминальной цепочкой, порождаемой грамматикой .

Язык, порождаемый грамматикой , обозначается - это множество всех терминальных цепочек, порождаемых грамматикой :

.