Загрузка...

ФОРМАЛЬНЫЕ ГРАММАТИКИ


Определение. ФОРИАЛЬНОЙ ГРАММАТИКОЙ называется формальная система, состоящая из четырех объектов
, где
— алфавит терминальных знаков,
— алфавит нетерминальных знаков,
причем ,
— аксиома или начальный нетерминальный знак ,
— конечное множество продукций или же правил вывода. То есть — это всевозможные строки вида (из выводится ), где есть строки в объединенном алфавите терминальных и нетерминальных знаков (или же строки принадлежат множеству универсум над объединенным алфавитом).

Есть смысл потребовать, чтобы строка не была пустой ( ). То есть  .

Пример. Рассмотрим грамматику симметричных строк .
Определим алфавиты:
Тогда можем сделать вывод в грамматике и убедиться что данная грамматика есть грамматика симметричных строк.

Формальные грамматики используются как конечная форма бесконечных языков.

СТРОГОЕ ОПРЕДЕЛЕНИЕ ВЫВОДА В ГРАММАТИКЕ.

Пусть есть грамматика и есть вывод в грамматике , тогда
вывод в грамматике определим индуктивно:

Шаг 0. — есть аксиома.

Шаг k. Предположим, что в результате вывода в грамматике получена строка , где , тогда

Шаг m. Завершаем вывод в грамматике , когда получаем строку , состоящую из знаков терминального алфавита ( ).

Определение. СЕНТЕНЦИАЛЬНАЯ ФОРМА ГРАММАТИКИ — это такая строка , что существует последовательность вывода в грамматике , оканчивающаяся строкой .То есть ( ).

Определение. СЕНТЕНЦИЯ (ПРЕДЛОЖЕНИЕ) грамматики называется сентенциальная форма, состоящая из знаков терминального алфавита. То есть это есть строка .

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

Определение. ФОРМАЛЬНЫМ ЯЗЫКОМ , порожденным формальной грамматикой
, называется множество всех сентенций грамматики . То есть это такие строки в терминальном алфавите, что могут быть получены из аксиомы грамматики путем применения продукций . .

Определение. ЭКВИВАЛЕНТНЫМИ ГРАММАТИКАМИ такие грамматики и , которые порождают один и тот же язык, то есть множество строк равны. . Обозначим как ~ .

ФОРМЫ ЗАДАНИЯ ФОРМАЛЬНЫХ ГРАММАТИК.

1. Формальная форма задания формальных грамматик.
Пример. .

2. Нотация Бэкуса – Наура.
1. Нетерминальные знаки обозначают монятия языка и записываются в виде названия этого понятия, заключенного в скобки без пробелов .
2. Вместо знаков вывода в продукции используется знак .
3. Знак | означает альтернативное задание правых частей продукции. Если знак | используется в алфавите языка, то альтернативное задание правых частей продукции производится на новой строке текста.

Пример: Задание формальной грамматики целое число.

Загрузка...