Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 6 стр.

      Тип 2. Грамматика G = (VT , V N , P, S ) называется контекстно-свободной
грамматикой (КС-грамматикой), если ее правила вывода имеют вид: A → β ,
где A∈VN и β ∈V * .
      Тип 3. Грамматика G = (VT , V N , P, S ) называется регулярной граммати-
кой (Р-грамматикой) выровненной вправо, если ее правила вывода имеют вид
 A → aB | a , где a ∈VT ; A, B ∈V N .
      Грамматика G = (VT , V N , P, S ) называется регулярной грамматикой (Р-
грамматикой) выровненной влево, если ее правила вывода имеют вид
 A → Ba | a , где a ∈VT ; A, B ∈V N .
  Определение 1.12. Язык L(G) называется языком типа k, если его можно опи-
 сать грамматикой типа k, где k – максимально возможный номер типа грамма-
                                      тики.
     Соотношение типов грамматик и языков представлено на рисунке 1.1.


                                   Тип 0
                              КЗ
                         КС
                     Р




                        Р – регулярная грамматика;
                  КС – контекстно-свободная грамматика;
     КЗ – контекстно-зависимая грамматика;
     Тип 0 – грамматика типа 0.

      Рисунок 1.1 – Соотношение типов формальных языков и грамматик
  Пример 1.6. Примеры различных типов формальных языков и грамматик по
классификации Хомского. Терминалы будем обозначать строчными символами,
   нетерминалы – прописными буквами, начальный символ грамматики – S.
                                    2
                                        −1
     а) Язык типа 0 L(G)={ a 2b n            | n ≥ 1 } определяется грамматикой с прави-
лами вывода:
     1) S → aaCFD;                      2) AD → D;
     3) F → AFB | AB;                   4) Cb → bC;
     5) AB → bBA;                       6) CB → C;
     7) Ab → bA;                        8) bCD → ε.
     б) Контекстно-зависимый язык L(G)={anbncn | n≥1} определяется грамма-
тикой с правилами вывода:
     1) S → aSBC | abc;        2) bC → bc;

6