Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 20 стр.

                                                                              20
            3. КЛАССИФИКАЦИЯ ГРАММАТИК. ИЕРАРХИЯ
                          ХОМСКОГО.
      Ограничение типов правил, которые могут появляться в грамматике
позволяет определить ряд специальных классов грамматик. Одна из
стандартных классификаций известна как иерархия Хомского. Ее описывают
следующим образом:
1. Любая грамматика определенного ранее вида – грамматика типа 0.
2. Если для всех правил вида α → β, |α| ≤ |β|, где |α| и |β| – длина, т.е. число
символов соответственно α и β, то грамматика называется грамматикой
типа 1, или контекстно-зависимой (КЗ).
3.   Если   все   левые   части   правил   грамматики     состоят   из   одного
нетерминального символа, то это грамматика типа 2, или контекстно-
свободная (КС).
4. Грамматика называется грамматикой типа 3, или регулярной, если
каждое правило грамматики имеют одну из следующих форм.
      В случае грамматики, выровненной вправо, в правой части грамматики
имеется не более одного нетерминала, который может быть только самым
правым символом:
      A→a
      A → aB
      B случае грамматики, выровненной влево, в правой части грамматики
имеется не более одного нетерминала, который может быть только самым
левым символом:
      A→a
      A → Ba
      Иерархия – включающая, т.е. все грамматики типа 3 являются
грамматиками типа 2 и т.д. Иерархия грамматик соответствует иерархии
языков. Например, если язык можно генерировать с помощью грамматики
типа 2, то его называют языком типа 2. Необходимо помнить, что если для