Математика: Разное.

Минимизация автомата

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

0. Инициализируем новый автомат одним начальным состоянием.
   далее будем состояния добавлять.
1. Строим очередь из состояний старого автомата, инициализируя
ее начальным состоянием автомата.
2. Строим словарь из состояний старого автомата в
состояния нового автомата, инициализируя его соответствием
начальных состояниий автоматов.
3. Цикл: пока очередь непуста.
  3а) извлекаем из нее состояние старого,
      назовем его рабочим.
  3б) добавляем в таблицу переходов нового
  автомата строку, которую будем заполнять в цикле
  4в) Цикл по всему алфавиту:
      4ва) Подаем на вход автомата i-й символ языка
      4вб) Проверяем, есть ли новое состояние старого
           автомата в словаре
      4вв) Если нет,
           4вва) добавляем состояние новому автомату
           4ввб) добавляем соответствие состояний в словарь
           4ввв) добавляем состояние старого
                 автомата в очередь
      4вг) заполняем клеточку в таблице переходов нового автомата.
           (образ [по словарю] рабочего состояния при подаче на вход
            текущего символа перейдет в образ нового состояния)
конец.

Вверх по странице, к оглавлению и навигации.