Диаграмма грамматики.

Пусть дана А-грамматика G=< V_T,V_N, S, R> . Диаграмма А-грамматики – граф с помеченными вершинами и дугами. Множество вершин графа соответствует множеству нетерминалов А-грамматики, приведенной к каноническому виду, а множество дуг – множеству правил грамматики.

Преобразование грамматики:

Вводим дополнительный нетерминальный символ К.V_N =V_NÈ{К}

Заменяем правила вида А®а на правила А®аК.

Вводим дополнительное правило К®l

Таким образом, все правила грамматики теперь приобрели "стандартный" вид A®aBили A®l.

Построение диаграммы опишем следующими правилами.

1. Каждому нетерминальному символу поставим в соот­ветствие вершину и пометим ее этим символом.

2. Каждому правилуA®aBсопоставим дугу из верши­ны A в вершину В и пометим ее терминальным символом а.

3. Отметим в графе как начальную вершину - вершину, со­ответствующую начальному символу, и как заключительные - все такие вершины В, что B®l(на диаграмме используется символ #).

Пример. Пусть грамматика G₈описывается правилами:

S ®aBïbC B ®bïbB C® aS

Грамматика в канонической форме будет иметь вид:

 

S ®aBïbC B ®bKïbB C® aS K® l

Диаграмма грамматики приводится на рис.1.

Рис.1

Очевидно, что существует взаимно-однозначное соответсвие между грамматикой в каноническом виде и диаграммой.

Например, рассмотрим диаграмму грамматики, представленную на рис.2.

Рис.2

Очевидно, что диаграмме соответствует грамматика G₉ с правилами

 

S ®aSïaB B ®bKïbB K® l