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

68                                                              Глава 4. Теория автоматов


ствует такая биекция σ : S → S 0 , что
                        sδ(x) = t ⇔ (sσ)δ 0 (x) = tσ
или, в более краткой форме,
                               (sσ)δ 0 (x) = sδ(x)σ                                  (1)
для всех s ∈ S, x ∈ X.
   Упражнение 1. Доказать, что автоматы изоморфны в том и
только том случае, когда изоморфны их графы, причём соответству-
ющие при этом изоморфизме дуги имеют одинаковые метки.
   Настроенные автоматы
                         (S, δ, so , F ) и (S 0 , δ 0 , s00 , F 0 )                  (2)
назовём изоморфными, если дополнительно к условию (1) верно
                        s0 σ = s00 , s ∈ F ⇔ sσ ∈ F 0 .                              (3)
Очевидно, что изоморфные автоматы распознают один и тот же язык.
Замечательно, что для минимальных автоматов верно и обратное:
   Теорема 1. Если настроенные минимальные автоматы распо-
знают один и тот же язык, то они изоморфны.
   Д о к а з а т е л ь с т в о. Предположим, что автоматы (2) удо-
влетворяют условию теоремы. Рассмотрим множество пар состояний
                        {(s0 δ(p), s00 δ 0 (p)) : p ∈ X ∗ }.                         (4)
Легко усмотреть, что эти пары состоят из эквивалентных состояний.
Ввиду связности первого автомата каждое из состояний s ∈ S по-
является в качестве левого элемента пары, а в силу приведённости
второго автомата появляется ровно один раз. Действительно, предпо-
ложим, что некоторое s входит в две пары. Тогда s = s0 δ(p) = s0 δ(q)
и s00 δ(p) 6= s00 δ(q) для некоторых слов p и q. Получается, что нерав-
ные состояния второго автомата эквивалентны, поскольку они экви-
валентны одному и тому же состоянию первого автомата — противо-
речие с приведённостью. По аналогичным причинам каждое из состо-
яний s0 ∈ S 0 появляется в множестве (4) в качестве правого элемента
пары ровно один раз. А это значит, что множество (4), сопоставляю-
щее состоянию s0 δ(p) первого автомата эквивалентное ему состояние
s00 δ 0 (p) второго автомата, задаёт биекцию из S в S 0 . Обозначим её
через σ и проверим выполнение условия (1). Пусть s = s0 δ(p), тогда
sσδ 0 (x) = s00 δ 0 (p)δ 0 (x) = s00 δ 0 (px) = s0 δ(px)σ = s0 δ(p)δ(x)σ = sδ(x)σ.