Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 13 стр.

    3 Лабораторная работа № 3. Минимизация конечных авто-
матов

      Цель: - закрепить понятия «недостижимые состояния автомата», «экви-
валентные состояния автомата», «минимальный конечный автомат»;
            - сформировать умения и навыки минимизации детерминированно-
го конечного автомата.
                                   Основы теории
      Конечный автомат может содержать лишние состояния двух типов: не-
достижимые и эквивалентные состояния.
      Определение 3.1. Два различных состояния q и q′ в конечном автомате
M = (Q, T , F , H , Z ) называются n-эквивалентными, n∈N∪{0}, если, находясь в
одном их этих состояний и получив на вход любую цепочку символов ω:
ω ∈VT*, |ω|≤n, автомат может перейти в одно и то же множество конечных со-
стояний.
      Определение 3.2. Состояние q КА называется недостижимым, если к не-
му нет пути из начального состояния автомата.
      Определение 3.3. КА, не содержащий недостижимых и эквивалентных
состояний, называется приведенным или минимальным КА.

          Алгоритм 3.1. Устранение недостижимых состояний КА
     Вход: КА M = (Q, T , F , H , Z ) .
     Выход: КА M ′ = (Q′, T , F ′, H , Z ′) .

     Шаг 1. Поместить начальное состояние КА в список достижимых состоя-
ний Qд , т.е. Qд0 = H .
     Шаг 2. Для новых элементов списка достижимых состояний пополнить
список группой их состояний-приемников, отсутствующих в нем, т.е.
Qдi = Qдi −1 ∪ { p | ∀q ∈ Qдi −1 ∃ F (q, t ) = p} .
      Шаг 3. Повторить шаг 2, пока список достижимых состояний не переста-
нет меняться. То есть, если Qдi ≠ Qдi −1 , то i:=i+1, иначе Qд = Qдi .
       Шаг 4. Исключить из множества Q состояний КА все состояния, отсутст-
вующие в списке Qд достижимых состояний, т.е. Q′ = Q ∩ Qд .
       Шаг 5. Исключить недостижимые заключительные состояния и пары
функции переходов, содержащие недостижимые состояния, т.е. Z ′ = Z ∩ Qд ,
F ′ = F − {F (q, t ) = p | q ∈ (Q − Qд )} .

      Пример 3.1. Устранить недостижимые состояния КА M = (Q, T , F , H , Z ) ,
где Q = {A, B, C, D, E, F, G}, T = {a, b}, H = {A}, Z = {D, E} и функция перехо-
дов задана таблицей 3.1. Граф исходного КА М представлен на рисунке 3.1.

                                                                              13