Специальная математика. Соловьев А.Е. - 75 стр.

  ::= 
  VN - нетерминальный символ;
    V*\{}:
Здесь также представляют наибольший            интерес   грамматики   непосредственных
составляющих.

Такие грамматики называются контекстно-свободными грамматиками или                КС-
грамматиками.
Языки программирования большей частью описываются грамматиками этого типа.

Тип 3 . К этому типу относятся грамматики, правила которых имеют один из двух видов:
   A := Bc
   A := b 
 где A, B, C VN ; b,c  VT ;
Это так называемый леворекурсивный вариант. В качестве альтернативы возможен и
праворекурсивный вариант:
   A := сB
   A := b 
Такие грамматики называют регулярными или автоматными грамматиками.
Лексический анализ в компиляторе обычно наиболее целесообразно описывать с помощью
этих грамматик.




                          7.4. Распознающие автоматы

Распознающим называется автомат Мура с множеством выделенных состояний, называемых
конечными. Говорят, что автомат распознает входное слово, если, начав свою работу в
одном из начальных состояний, он заканчивает ее в одном из конечных.
Пример: Автомат, распознающий слова содержащие попарное вхождение букв а
 и b, вроде aabbbbaa. f1, f2 - конечные состояния




                     2                a
                              a
            b                         f1
     a,b            a    a

     4               1
                          b
                a    b
                                  b f2

                     3
                                  b

                                           — 75 —