Основы трансляции - 13 стр.

   Видно, что это недетерминированный КА (из состояния            возможны два
различных перехода по символу ).
   Построим множество состояний эквивалентного ДКА:

                                                      .
  Построим функцию переходов эквивалентного ДКА:
                ,                         ,                               ,
                  ,                          ,                            ,
                ,                           ,                                 ,
                      ,                   ,                               ,
                    ,                          ,                                  ,
                    ,                             ,
                   ,                             ,  .
  Начальное состояние эквивалентного ДКА:            .
  Множество конечных состояний эквивалентного ДКА:

  После построения ДКА исключим недостижимые состояния. Множество
достижимых состояний ДКА будет следующим:                      . В
итоге, исключив все недостижимые состояния, получим ДКА:
                                                           ,
  где                ,            ,               ,          .
  Ничего не изменяя, переобозначим состояния ДКА. Получим:
                                                      ,
  где            ,           ,           ,          .
  Граф переходов полученного ДКА изображен на рис. 2.




         Рис 2. Граф переходов детерминированного конечного автомата
  Этот автомат можно преобразовать к полностью определенному виду.
Получим граф состояний, изображенный на рис. 3 (состояние - это состояние
«ошибка»).




              Рис 3. Граф переходов полностью определенного ДКА
                                     13