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

      Не менее просто осуществляется переход для автомата, заданного в таб-
личной форме. Это можно увидеть, если для рис. 3 нарисовать соответствую-
щие таблицы переходов и выходов (табл. 6 и 7).

                 Таблица 6                         Таблица 7
                    qн       qч                       qн       qч
             1      qч       qн                1      ч        н
             2      qн       qч                2      н        ч
             3      qч       qн                3      ч        н


       В этом случае таблица переходов дублирует существующую, а таблица
выходов получается заменой в таблице переходов состояний, в которые перехо-
дит автомат, на выходные сигналы, которые этим состояниям были приписаны
в автомате Мура.



                         МИНИМИЗАЦИЯ АВТОМАТОВ


       Минимальный автомат- это автомат, имеющий наименьшее возможное
количество состояний и реализующий заданную функцию выходов.
       Два состояния автомата называются 1-эквивалентными, если, находясь в
любом из этих состояний, автомат на один и тот же входной сигнал (входное
слово длиной в 1) выдает один и тот же выходной сигнал. Два состояния авто-
мата называются К- эквивалентными, если, начиная с любого из этих состояний,
автомат на любые одинаковые слова длины К выдает одинаковые выходные
слова (также длины К). Если два состояния К- эквивалентны для любых К, то их
называют (просто) эквивалентными. Множество попарно эквивалентных со-
стояний образует класс эквивалентности.
       Смысл минимизации состоит в выявлении классов эквивалентности и
замене каждого класса одним состоянием.
       Процедура минимизации состоит в следующем:
       1. По таблице выходов автомата Мили (или по первой строке отмечен-
          ной таблице переходов автомата Мура) находятся состояния, имею-
          щие одинаковые столбцы (отмеченные одинаковыми выходными
          сигналами) – это 1-эквивалентные состояния.
       2. Далее используется таблица переходов. Все состояния, входящие в 1-
          эквивалентный класс, которые под воздействием первого сигнала пе-
          решли в состояния, принадлежащие в свою очередь 1-
          эквивалентному классу, образуют 2-эквивалентный касс.
       3. Процедура разбиения на классы эквивалентности продолжается до те
          пор, пока при очередном шаге К- эквивалентные классы не совпадут
          с (К-1)-эквивалентными, т.е. получатся эквивалентные классы.
       4. Все состояния, входящие в один класс эквивалентности, заменяются
          одним состоянием.
       Пример. Рассмотрим автомат Мили заданный табл. 8 и 9.