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

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

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

КС-грамматика 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, новые символыидобавляются во множество нетерминальных символов VN’ грамматики G’.

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

А 



…



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

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

Статьи к прочтению:

Определяем тип формальной грамматики и языка по классификации Хомского.

Похожие статьи: