Нормальная форма Хомского или бинарная нормальная форма (БНФ) – это одна из предопределенных форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую произвольную КС-грамматику. Для преобразования в нормальную форму Хомского предварительно грамматику надо преобразовать в приведенный вид.
Определение нормальной формы Хомского
КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Хомского, если в ее множестве правил Р присутствуют только правила следующего вида:
1. А ВС, где A,B,CVN.
2. А а, где AVN и aVT.
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. Если встречается правило вида Аа, где AVN и aVT, то оно переносится во множество Р’ без изменений.
2. Если встречается правило вида АВС, где A,B,CVN, то оно переносится во множество Р’ без изменений.
3. Если встречается правило вида S, где S – целевой символ грамматики G, то оно переносится во множество Р’ без изменений.
4. Если встречается правило вида АаВ, где A,BVN и aVT, то во множество правил Р’ включаются правила А<АаВ>В и <АаВ>а и новый символ <АаВ> добавляется во множество нетерминальных символов VN’ грамматики G’.
5. Если встречается правило вида АВа, где A,BVN и aVT, то во множество правил Р’ включаются правила АВ<АВа> и <АВа>а, и новый символ <АВа> добавляется во множество нетерминальных символов VN’ грамматики G’.
6. Если встречается правило вида Aab, где AVN и a,bVT, то во множество правил Р’ включаются правила А<Аа><Аb>, <Аа>а и <Ab>b, новые символы <Аа> и <Аb> добавляются во множество нетерминальных символов VN’ грамматики G’.
7. Если встречается правило вида AX1...Xk, k>2, где AVN и i: XiVTVN, то во множество правил Р’ включается цепочка правил:
А <X1’><X2...Xk>
<X2...Xk> <X2’><X3...Xk>
…
<Xk-1Xk> <Xk-1’><Xk>
Новые нетерминальные символы <X2...Xk>,...,<Xk–1Xk> включаются во множество нетерминальных символов VN’ грамматики G’, кроме того, i: если XiVN, то <Xi’>=Xi, иначе (если XiVT) <Xi’> – это новый нетерминальный символ, он добавляется во множество VN’, а во множество правил Р’ грамматики G’ добавляется правило <Xi’> Xi.
Целевым символом результирующей грамматики G’ является целевой символ исходной грамматики G.
