Грамматики в нормальной форме Хомского

Нормальная форма Хомского или бинарная нормальная форма (БНФ) – это одна из предопределенных форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую произвольную КС-грамматику. Для пре­образования в нормальную форму Хомского предварительно грамматику надо преобразовать в приведенный вид.

Определение нормальной формы Хомского

КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Хомского, если в ее множестве правил Р присутствуют только правила следую­щего вида:

1. А  ВС, где A,B,CVN.

2. А  а, где AVN и aVT.

3. S , если L(G), причем S не должно встречаться в правых частях других правил.

Никакие другие формы правил не должны встречаться среди правил граммати­ки в нормальной форме Хомского.

КС-грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ). Название “бинарная” происходит от того, что на каждом шаге вывода в такой грамматике один нетерминальный символ может быть заменен только на два других нетерминальных символа. Поэтому в дереве вывода грамматики в нормальной форме Хомского каждая вершина либо распадается на две другие вершины (в соответствии с первым видом правил), либо содержит один последующий лист с терминальным символом (в соответст­вии со вторым видом правил). Третий вид правил введен для того, чтобы к нор­мальной форме Хомского можно было преобразовывать грамматики КС-языков, содержащих пустые цепочки символов.

Алгоритм преобразования грамматики в нормальную форму Хомского

Алгоритм позволяет преобразовать произвольную исходную КС-грамматику в эквивалентную грамматику в нормальной форме Хомского.

Условие: дана КС-грамматика G(VT,VN,P,S), необходимо построить эквивалентную ей грамматику G’(VT,VN’,P’,S’) в нормальной форме Хомского: L(G) =L(G’).

На первом шаге исходную грамматику надо преобразовать к приведенному виду. Поскольку алгоритм преобразования КС-грамматик к приведенному виду был рассмотрен выше, можно считать, что исходная грамматика уже является приве­денной (не содержит бесполезных и недостижимых символов, цепных правил и -правил).

В начале работы алгоритма преобразования приведенной КС-грамматики в нор­мальную форму Хомского множество нетерминальных символов VN’ результи­рующей грамматики G’ строится на основе множества нетерминальных симво­лов VN исходной грамматики G: VN’ = =VN.

Затем алгоритм преобразования работает с множеством правил Р исходной грам­матики G. Он просматривает все правила из множества Р и в зависимости от вида каждого правила строит множество правил Р’ результирующей граммати­ки G’ и дополняет множество нетерминальных символов этой грамматики VN’.

1. Если встречается правило вида Аа, где AVN и aVT, то оно переносится во множество Р’ без изменений.

2. Если встречается правило вида АВС, где A,B,CVN, то оно переносится во множество Р’ без изменений.

3. Если встречается правило вида S, где S – целевой символ грамматики G, то оно переносится во множество Р’ без изменений.

4. Если встречается правило вида АаВ, где A,BVN и aVT, то во множество правил Р’ включаются правила А<АаВ>В и <АаВ>а и новый символ <АаВ> добавляется во множество нетерминальных символов VN’ граммати­ки G’.

5. Если встречается правило вида АВа, где A,BVN и aVT, то во множество правил Р’ включаются правила АВ<АВа> и <АВа>а, и новый символ <АВа> добавляется во множество нетерминальных символов VN’ граммати­ки G’.

6. Если встречается правило вида Aab, где AVN и a,bVT, то во множество правил Р’ включаются правила А<Аа><Аb>, <Аа>а и <Ab>b, новые символы <Аа> и <Аb> добавляются во множество нетерминальных симво­лов VN’ грамматики G’.

7. Если встречается правило вида AX1...Xk, k>2, где AVN и i: XiVTVN, то во множество правил Р’ включается цепочка правил:

А  <X1’><X2...Xk>

<X2...Xk>  <X2’><X3...Xk>

…

<Xk-1Xk>  <Xk-1’><Xk>

Новые нетерминальные символы <X2...Xk>,...,<Xk–1Xk> включают­ся во множество нетерминальных символов VN’ грамматики G’, кроме того, i: если XiVN, то <Xi’>=Xi, иначе (если XiVT) <Xi’> – это новый нетер­минальный символ, он добавляется во множество VN’, а во множество пра­вил Р’ грамматики G’ добавляется правило <Xi’>  Xi.

Целевым символом результирующей грамматики G’ является целевой символ исходной грамматики G.