Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 47 стр.

      5.7.3. Равносильность автоматов Мили и Мура
     Равносильность заключается в том, что множество реакций этих автоматов совпадает:
     L(M) = {qz | qZ ∈ K};
     L(U) = {ht | ht ∈ K1};
     L(M) = L(U).
     Теорема. Для каждого автомата Мура можно построить равносильный автомат Мили.
     Доказательство. Граф равносильного автомата Мили M можно получить в том случае,
если каждому ребру автомата Мура U сопоставить ребро автомата M.
     Пусть w = x1 x2 ... xn - входная цепочка, тогда множества реакций для автоматов M и U
будут соответственно представлены следующим образом:
     q0 / y1, x1 → q1 / y2, x2 → ... → qn-1 / yn, xn;
     q0, x1 / y1 → q1, x2 / y2 → ... → qn-1, xn / yn.
     Теорема. Для любого автомата Мили можно построить эквивалентный автомат Мура.
     Доказательство. В качестве множества K1 автомата Мура возьмем K1 = K ⋅ Y. Для
обеспечения равносильности автоматов M = U функции переходов и выходов определим
следующим образом:
     f1(p ⋅ y, a) = {qb | f(p, a) = q, b ∈ X};
     h(p ⋅ y) = y.
     Если реакция автомата M на входную цепочку вида w = x1 x2 ... xn из состояния q0 имеет
вид
                            q0, x1 / y1 → q1, x2 / y2 → ... → qk-1, xk / yk        (1),
         то существует такое состояние q0⋅x1 недетерминированного автомата U, что, начиная
работу из этого состояния, автомат U выполняет следующие действия:
                            q0 ⋅ x1 / y1 → q1 ⋅ x2 / y2 → ... → qk-1 ⋅ xk / yk, xk (2).
     Аналогично можно доказать и обратную теорему о том, что из существования реакции
(2) следует существование реакции (1), что подтверждает равносильность автоматов Мили и
Мура.

      5.7.4. Задания для самостоятельной работы.
    1. Построить конечный преобразователь, моделирующий работу светофора. Рассмотреть
различные алгоритмы переключения светофора.
    2. Построить автомат Мили, который читает текст, написанный на русском языке.
Автомат должен считать все слова, начинающиеся с символа "б" и оканчивающиеся
символом "т", т.е. такие, как "бит", "байт", "батут" и т.д. При построении автомата все
буквы кроме "б" и "т" можно обозначить каким-либо символом, например, "|".
    3. Построить автомат Мили, который читает программу, написанную на языке
программирования высокого уровня. Автомат должен считать все целые константы.




                                        ЗАКЛЮЧЕНИЕ

    Всякий алгоритм можно рассматривать как некоторое универсальное средство для
решения целого класса задач. Но существуют такие классы задач, для решения которых нет
общего универсального алгоритма. Проблемы решения такого рода задач называются
алгоритмически неразрешимыми проблемами. Однако алгоритмическая неразрешимость
проблемы решения задач того или иного класса не означает невозможность решения любой
частной задачи из этого класса. Переход от интуитивного понятия алгоритма к формальному
определению алгоритма (рекурсивные функции, машины Тьюринга) позволяет доказать
алгоритмическую неразрешимость ряда проблем.