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

Question

У меня есть вопрос по этому вопросу:

L = пусто, где алфавит {a,b}

как создать грамматику для этого? как может быть производственное правило? заранее спасибо

Answer 1

Грамматика G - это упорядоченный 4-кортеж {S, N, E, e, P}, где:

1. N - набор нетерминальных символов
2. E является набором терминальных символов
3. N и E не пересекаются
4. E является надмножеством алфавита L(G)
5. е пустая строка
6. P - множество упорядоченных пар элементов (NUEU e) ; то есть P является подмножеством (NUEU 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

или же

S := aSb

или же

S := aXb | XXSSX
X := aabbXbbaaS

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