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

      Шаг 1. На первом шаге строим нулевое разбиение R(0), состоящее из двух
классов эквивалентности: заключительные состояния КА - Z и не заключитель-
ные - Q-Z.
      Шаг 2. На очередном шаге построения разбиения R(n) в классы эквива-
лентности включить те состояния, которые по одинаковым входным символам
переходят в n-1 эквивалентные состояния, т.е.
              R(n) = {ri (n) : {qij ∈ Q : ∀t ∈ T F (qij , t ) ⊆ r j (n − 1)} ∀i, j ∈ N } .

     Шаг 3. До тех пор, пока R(n) ≠ R(n-1) полагаем n:=n+1 и идем к шагу 2.
     Шаг 4. Переобозначить оставшиеся неразбитые группы состояний и
включить их в таблицу новых обозначений состояний автомата.
     Шаг 5. Определить эквивалентный КА M ′′ в новых обозначениях.
      Пример 3.2. Минимизировать конечный автомат из примера 3.1.
      Последовательность построения разбиений будет иметь вид:
      R(0) = {{A, B, C}, {D, E}}, n = 0;
      R(1) = {{A}, {B, C}, {D, E}}, n = 1;
      R(2) = {{A}, {B, C}, {D, E}}, n=2.
      Т.к. R(1) = R(2), то искомое разбиение построено.
      Переобозначим оставшиеся неразбитые группы состояний:
      X={B, C}, Y={D, E}.
      Получим минимальный автомат M ′′ , где Q′′ ={A, X, Y}, Z ′′ ={Y}.

      Функция переходов автомата M ′′ представлена в таблице 3.3.
      Таблица 3.3 - Функция переходов автомата M ′′
               F ′′                     A                  X                   Y
               a                        X                                      X
               b                        X                  Y                   Y
     Граф переходов конечного автомата после его минимизации показан на
рисунке 3.3.

                                                           b
                                 a, b           b
                            A               X          Y
                                                a

                        Рисунок 3.3 – Граф минимального КА M ′′
                      Постановка задачи к лабораторной работе № 3
      Разработать программное средство, реализующее следующие функции:
      1) ввод исходного конечного автомата и вывод на экран его графа;
      2) устранение недостижимых состояний конечного автомата;
                                                                                       15