Построить грамматику для языка

Грамматика G — это упорядоченная четверка {S, N, E, e, P}, где:

1. N — набор нетерминальных символов
2. E представляет собой набор терминальных символов
3. N и E не пересекаются
4. E является надмножеством алфавита L(G)
5. e - пустая строка
6. P — множество упорядоченных пар элементов из (N U E U e); то есть P является подмножеством (N U E U e) X (N U E U e)*.
7. S, начальный символ, находится в N

Вывод в G — это последовательность элементов из (N U E U e)* такая, что:

1. Первый элемент S
2. Смежные элементы w[i] и w[i+1] могут быть записаны как w[i] = uxv и w[i+1] = uyv так, что (x, y) принадлежит P

Если в G существует порождение, последним элементом которого является строка w[n] над (E U e)*, мы говорим, что G порождает w[n]; то есть w[n] принадлежит L(G).

Теперь мы хотим определить грамматику G, для которой L(G) — пустое множество. Зафиксируем алфавит E = {a, b}. Мы должны еще определить:

1. N, множество нетерминалов
2. S, стартовый символ
3. П, производство

С тем же успехом мы могли бы взять S в качестве начального символа. Итак, N содержит по крайней мере S; N является надмножеством {S}. Мы добавим больше нетерминалов только в том случае, если решим, что они нам нужны. Обратим внимание на условие пустоты L(G).

Если L(G) пусто, это означает, что в G нет вывода, который приводит к строке только терминальных символов. Мы можем легко добиться этого, обеспечив, чтобы все наши производства производили по крайней мере один нетерминал с любым терминалом. Или вообще не производить терминалы. Таким образом, все следующие грамматики будут работать:

S := S

or

S := aSb

or

S := aXb | XXSSX
X := aabbXbbaaS

и т. д. Все эти грамматики имеют пустую L(G), поскольку ни одна из них не может вывести строку нетерминалов.