Теория автоматов. - 13 стр.

                     рис. 12                                рис 13.

      П р и м е ч а н и е . Для данного содержательного описания частичный
недетерминированный распознающий автомат может иметь вид рис. 13, где
1 – начальное состояние, а F –заключительное. Соответствующая автоматная
грамматика может быть записана как:
                           1 ::= б / б2
                           2 ::= б2 / ц2 / б / ц

         1.6. Этот «безобидный» с виду автомат требует, судя по всему, 21 со-
              стояния. Не полностью ( для наглядности) заполненная табл.15 ил-
              люстрирует возможное решение. Начальное состояние 0 использу-
              ется только на первом шаге. Следует обратить внимание на появле-
              ние состояния 5.




                                     Таблица 15

    О О О О О О О О О О П О О О О О О О О О Р
     0     5   10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

х10 10 15 20                         50                               100 5   10
х15 15 20                       50                               100 5   10 15
х25 20                     50                                100 5    10 15 20


      Но это первое приходящее в голову решение. А может быть, можно по-
строить более компактный автомат Мура?

         1.20. Решение может иметь           вид рис. 14.