Определение и общие свойства порождающих грамматик

Преобразуем нормальные формы Бекуса с целью сделать их более удобными для изучения математическими средствами и исключить ненужные элементы семантики. Для преобразования выполним следующие действия над каждой металингвистической формулой:

1) Заменим каждое понятие в угловых скобках символом, не входящим в множество основных символов. Множество таких символов назовем нетерминальными или вспомогательными.

2) Металингвистическую связку::= заменим на знак ®.

3) Каждую многовариантную формулу заменим на соответствующее число формул с одним вариантом.

4) Основные символы языка будем называть также терминальными символами, цепочки основных символов – терминальными цепочками.

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

Обозначим используемые в формулах конструкции буквами русского алфавита следующим образом: Ч – число, Н – число без знака, Д – десятичное число, П – порядок, М – правильная дробь, Ф – целое, Б – целое без знака, Ц – цифра.

Нормальные формы Бекуса после преобразований примут следующий вид: Таблица 1.

Ч ® Н	П ® eФ	Ц ® 2
Ч ® +Н	М ® Б	Ц ® 3
Ч ® –Н	Ф ® Б	Ц ® 4
Н ® Д	Ф ® +Б	Ц ® 5
Н ® П	Ф ® –Б	Ц ® 6
Н ® ДП	Б ® Ц	Ц ® 7
Д ® Б	Б ® БЦ	Ц ® 8
Д ® М	Ц ® 0	Ц ® 9
Д ® БМ	Ц ® 1

F Определение: Порождающей грамматикой G называется четверка объектов < V_Т, V_A, I, S >, где

V_Т – конечное множество (словарь) терминальных или основных символов;

V_A – конечное множество (словарь) нетерминальных или вспомогательных символов, V_Т Ç V_A = Æ;

I - начальный символ или аксиома грамматики, I Î V_A;

S – конечное множество правил вида x ® h, где x и h –цепочки, состоящие из терминальных и нетерминальных символов. Правила из S называются правилами вывода грамматики G.

_* _* Þ

F Определение: 1) Говорят, что цепочка w ₁ непосредственно выводима из цепочки w ₀ в грамматике G (w ₀ Þ w ₁), если w ₀ = x ₁ x x ₂, w ₁ = x ₁ hx ₂,где x ₁ ,x, x ₂ и h – некоторые цепочки над объединением словарей грамматики G, и правило x ® h является ее правилом вывода.

2) Говорят, что цепочка w _n выводима из цепочки w ₀ в грамматике G (w ₀ w _n), если $ w _i, i = 1..n: w _i_-1Þ w _i.

3) Если из w ₀ выводится цепочка w_n и w ₀ = А Î V_A, то говорят, что цепочка w_n выводима из символа А, w_n - терминальная цепочка.

4) Совокупность терминальных цепочек грамматики G, выводимых в ней из начального символа, называется языком, порождаемым этой грамматикой, и обозначается через L (G).

Одной из основных проблем, связанных с практическим применением грамматик, является проблема распознавания.

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

Если такой алгоритм существует, то язык называется распознаваемым.

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

F Определение: Длиной цепочки w над некоторым словарем (обозначение l (w)), будем называть число символов, входящих в эту цепочку. Если l (w)=0, цепочка называется пустой. Пустую цепочку будем обозначать через e.

F Определение: Грамматика называется не укорачивающей, если для любого ее правила вывода x ® h справедливо неравенство l (x) £ l (h).

G Теорема 1: Язык L (G), порождаемый не укорачивающей грамматикой G, легко распознаваем.

Рассмотрим несколько классов грамматик:

Таблица 2.

НАЗВАНИЕ грамматик	ПРАВИЛА	ЗАМЕЧАНИЯ
Контекстно-зависимые	x ₁ A x ₂ ® x1h x2	x ₁ x ₂h – произвольные цепочки А – нетерминальный символ
Контекстно-свободные	А ® h	h – непустая цепочка А – нетерминальный символ
Укорачивающие контекстно-свободные	А ® h	h –может быть и пустой цепочкой А – нетерминальный символ
Автоматные	А ® bB, A ® b	А, В –нетерминальные символы, b – терминальный символ