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

                                                                          38
                                                   0,1
                           1
                                        B

                                                       0,1
                       A                    C

                                 0
      Рис.6.3. Переходы детерминированного конечного автомата M2.


     Как и М1, М2 принимает строки из нулей и единиц тогда и только тогда,
когда строка начинается с единицы. Однако при распознавании строки с
помощью М2 возврат никогда не требуется, т.к. в процессе чтения
определенного входного символа из любого состояния произойдет точно
один переход к другому состоянию. Это значит, что при использовании М2
время распознавания строки будет пропорционально ее длине.
     Соответствие лексическому анализу заключается в том, что каждому
языку типа 3 соответствует детерминированный конечный автомат, который
распознает   строки    этого   языка.   Например,     строки,   генерируемые
грамматикой G1c порождающими правилами:
     А → 1А | 1В | 1
     В → 0В | 1В | 0 | 1
где А – начальный символ, распознаются с помощью М1 или М2. Грамматику
получают из недетерминированного конечного автомата М1 следующим
образом:
     1. Начальное состояние автомата становится начальным символом
предложения грамматики.
     2. Переходам
     δ (А, 1) = А,                              δ (В, 0) = В,
     δ (А, 1) = В,                              δ (В, 1) = В.
соответствуют порождающие правила