Дискретная математика: графы и автоматы. Альпин Ю.А - 67 стр.

§ 3. Единственность минимального автомата                         67


    Если на некотором шаге все строки таблицы оказались заполнен-
ными, то построение закончено. В том случае, когда rk L = ∞, оно
будет продолжаться неограниченно долго.
    Пример 2. Рассмотрим язык L, состоящий из слов вида pabbaq,
то есть, слов, содержащих подслово abba. Рекомендуем читателю
проверить, что описанный метод приводит к нижеследующей табли-
це. Рядом изображён соответствующий автоматный граф. Короткая
стрелка указывает на начальное состояние, единственное допускаю-
щее состояние обведено кружком.


            a     b
       e    a     e
       a    a    ab
       ab   a    abb
      abb abba    e
      abba abba abba




                                  Рис. 4




         § 3. Единственность минимального автомата

   Мы рассматриваем автоматы над некоторым фиксированным ал-
фавитом X. Говорят, что состояния s и s0 автомата (S, δ, F ) эквива-
лентны, если для любого слова p
                        sδ(p) ∈ F ⇔ s0 δ(p) ∈ F.
Настроенный автомат (S, δ, s0 , F ) называется
    1) связным, если для любого состояния s ∈ S найдётся такое сло-
во p, что s0 δ(p) = s;
    2) приведённым, если у него нет эквивалентных состояний.
    Связный и приведённый настроенный автомат называется мини-
мальным. Предлагаем доказать самостоятельно
    Предложение 1. Автомат A(L)      e   — минимальный.
   Автоматы (S, δ) и (S 0 , δ 0 ) называются изоморфными, если суще-