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

       5.7. Автоматы Мили и Мура
    Автоматы Мили и Мура являются неинициальными автоматами. В отображении S(x) =
g(q0, x) зафиксируем начальное состояние q0, в котором автомат находится в начальный
момент времени. Оно существенно влияет на процесс конечного преобразования, т.к.
определяет не только результирующую цепочку, но и множество входных цепочек.
   Рассмотрим поведение инициальных автоматов, которые могут начинать работать из
любого указанного состояния. Такой автомат получает на вход одну цепочку бесконечной
длины и перерабатывает её. Реакция такого преобразователя на определенные воздействия
непредсказуема, если неизвестно его начальное состояние. Поэтому необходимо решить две
задачи, имеющие важное практическое значение:
    1) определение того состояния автомата, в котором он находится в момент, начиная с
которого исследуется его поведение;
   2) распознавание конечного состояния, в которое перешел автомат после завершения
испытательной операции. Это состояние будет начальным для следующей серии испытаний.
   Эти задачи анализа получили название экспериментов по распознаванию состояния.

       5.7.1. Автомат Мили
    Автомат Мили - это пятерка вида M = (К, X, Y, f, g), где:
    K - множество состояний автомата;
    X - входной алфавит;
    Y - выходной алфавит;
    f - функция переходов (отображение K ⋅ X → K);
    g - функция выходов (отображение K ⋅ X → Y).
          Как и любой другой автомат, автомат Мили можно представить в виде таблицы
   или графа. В графе переходов автомата Мили на дугах указываются через символ ‘/’
   входные и выходные символы. Таблица переходов состоит из двух частей: в левой части
   записываются значения функции выходов, в правой части - значения функции переходов.
         Пример. Построим преобразователь,                который     распознает   арифметические
   выражения, порождаемые грамматикой:
                                            S → a+S | a−S | +S | −S | a


   и устраняет из этих выражений избыточные унарные операции. Например, выражение –
   a+−а−+−а он переведет в –а−а+а. Во входном языке символ а представляет идентификатор
   и перед идентификатором допускается произвольная последовательность знаков унарных
   операции + и −. Заметим, что входной язык является регулярным множеством.


           Пусть M = (К, X, Y, f, g), где
1. К = {q0, q1, q2, q3, q4},
2. X = {a,+, −},
3. Y = X.