Преобразование к нормальной форме Хомского

Каждая КС-грамматика G=(N, T, P, S) эквивалентна грамматике в нормальной форме Хомского с правилами вида:

1) А®ВС, где А, В, С ÎN;

2) А®a, где а ÎТ;

3) S®e, если e Î L(G), причем S не встречается в правых частях правил.

Дерево разбора любой строки языка в такой грамматике будет бинарным. Преобразование к нормальной форме Хомского (НФХ) полезно, когда требуется простая структура КС-языка. Оно выполняется путем сокращения количества символов правой части правила за счет введения новых обозначений (нетерминалов). Предварительно нужно привести исходную КС-грамматику.

Примечание: КС-грамматика обладает свойствами приведенной грамматики, если она не имеет циклов, e-правил и бесполезных символов. Отсутствие циклов означает, что в грамматике невозможны выводы вида АÞ+А, где А Î N.

Вход: КС-грамматика G=(N, T, P, S)

Выход: Эквивалентная КС-грамматика G’=(N’, T, P’, S) в НФХ

5. Включить в P’ каждое правило вида 2, т.е. (А®a) Î Р;

6. Включить в P’ каждое правило вида 1, т.е. (А®ВС) Î Р;

7. Включить в P’ каждое правило вида 3, т.е. (S®e) Î Р (если оно есть в Р);

8. Для каждого правила (А®X₁…X_k) Î Р, где k>2, включить в P’ правила:

А®X₁^’<X₂…X_k>

<X₂…X_k>® X₂’<X₃…X_k>

...

<X_k-2 X_k-1X_k>® X_k-2’< X_k-1X_k>

< X_k-1X_k>® X_k-1’X’_k

где <X_i…X_k> - новый нетерминал

X_i, если X_i ÎN

X_i’= X’_i, если X_i ÎT

9. Для каждого правила (А®X₁X₂) Î Р, где хотя бы один из символов X₁ и X₂ является терминалом, включить в P’ согласно обозначениям правило (А®X’₁X’₂)

10. Для каждого нового нетерминала вида X’, введенного в п.4 или в п.5, согласно обозначениям, включить в P’ правило X’®X, где XÎT

11. Пополнить множество нетерминалов V’_N = V’ È{новые нетерминалы}

При реализации алгоритма полезно иметь таблицу для обозначения терминалов и таблицу для обозначения строк из двух и более символов.

Пример. Преобразование в НФХ грамматики с правилами

S®aAВ | BA

А®ВBB|a

B®AS|b

Шаг алгоритма	Действия и результаты
	P’={ А®a, B®|b}
	P’={ А®a, B®|b} È { S® BA, B®AS }
	Правила S®e нет
	1) S®aAВ Терминал а обозначаем N1 Строка АВ обозначаем N2 Новые правила: S® N1 N2, N2 ®АВ 2) А®ВВВ Строка ВВ обозначаем N3 Новые правила: А® ВN3, N3 ®ВВ
	Таких правил нет
	Правило N1® а помещаем в P’: { S® N1 N2 | ВА, А® ВN3| a, B®AS| b, N2 ®АВ, N3 ®ВВ} È { N1® а }
	N’=NÈ{обозначения терминалов и строк}={S, A, B, N1, N2, N3}

Дата добавления: 2014-01-03