Алексеев В.Б. Лекции по дискретной математике, страница 11

Теорема об отличимости состояний двух автоматов.Будем рассматривать автоматы, в которых не выделено начальное состояние, то есть автомат задаётся пятёркой (A, B, Q, G, F).Через A* будем обозначать множество всех конечных слов в алфавите A. Расширимфункции F и G, определив F (a , qi ) и G (a , qi ) для любого состояния qi ∈ Q и любого словаa = (a(1), a (2),!, a(m )) ∈ A∗ . Пусть автомат (A, B, Q, G, F) находится в состоянии qi ∈ Q и навход подаётся слово a = (a(1), a (2),!, a(m )) . Тогда на выходе будет последовательно выдаваться некоторое слово b = (b(1), b(2),!, b(m )) и после подачи всего слова a автомат окажется в некотором состоянии qk.

Расширим функции F и G, положив F (a , qi ) = b , G (a , qi ) = qk .Определение 1. Два состояния qi и qj автомата (A, B, Q, G, F) называются отличимыми,если существует входное слово a ∈ A∗ такое, что F (a , qi ) ≠ F (a , q j ). При этом слово a назы-вают экспериментом, отличающим qi и qj, а длину l (a ) — длиной этого эксперимента.Лемма. Пусть в автомате (A, B, Q, G, F) есть 2 состояния qu и qv, отличимые экспериментом длины p и не отличимые более коротким экспериментом. Тогда для любого k, где1 ≤ k ≤ p, существуют 2 состояния, отличимые экспериментом длины k и не отличимые болеекоротким экспериментом.Доказательство.

Пусть состояния qu, qv отличимы экспериментом a длины p и не отличимы экспериментом меньшей длины. Пусть F (a , qu ) = b , F (a , qv ) = c . Тогда b ≠ c , причём b и c различаются только последней буквой. Разобьём все слова a , b , c на 2 подсловаa = a1a2 , b = b1b2 , c = c1c2 , где l (a2 ) = l (b2 ) = l (c2 ) = k . Пусть G (a1 , qu ) = q′ , G (a1 , qv ) = q′′ . ТогдаF (a2 , q′) = b2 , F (a2 , q′′) = c2 . Так как b2 и c 2 различаются последней буквой, то q' и q'' отли42чимы экспериментом длины l (a2 ) = k .

Допустим, что q' и q'' отличимы экспериментом a3длиныl (a3 ) < k .ТогдаF (a3 , q′) = b3 ,F (a3 , q′′) = c3иb3 ≠ c3 .НотогдаF (a1a3 , qu ) = b1b3 , F (a1a3 , qv ) = c1c3 и b1b3 ≠ c1c3 . Следовательно, qu и qv отличимы экспериментом a1a3 длины l (a1a3 ) = l (a1 ) + l (a3 ) < ( p − k ) + k = p . Это противоречит условию. Значит (отпротивного), q' и q'' не отличимы экспериментом длины меньшей, чем k. Лемма доказана.Теорема 3 (Теорема Мура).

Если в автомате (A, B, Q, G, F) состояния qi и qj отличимыи |Q| = r, то существует эксперимент a , отличающий qi и qj, длины l (a ) ≤ r − 1 .Доказательство. Пусть состояния qi и qj отличимы экспериментом длины p и не отличимы более коротким экспериментом. Рассмотрим в данном автомате следующее отношениеRm на множестве состояний Q (m = 0, 1, …, p): состояния qi и qj не отличимы экспериментомдлины m (считаем, что любые 2 состояния не отличимы экспериментом длины 0). Если длялюбого слова a ∈ A∗ длины m F (a , qi ) = F (a , q j ) и F (a , q j ) = F (a , qk ) , то F (a , qi ) = F (a , qk ) ,поэтому Rm — это отношение эквивалентности для каждого m = 0, 1, …, p. Относительно RmQ разбивается на классы эквивалентности Q1(m ), Q2(m ) ,!, Qs((mm)) , так что любые два состояния изодного класса не отличимы экспериментом длины m, а любые два состояния из разных классов отличимы экспериментом длины m.

При этом s(0) = 1 и Q = Q1(0 ) . Посмотрим, как меняются эти классы при переходе от m к m + 1. Если 2 состояния отличимы экспериментом длины m, то они отличимы и экспериментом длины m + 1, поэтому состояния из разных классовостаются в разных классах. По лемме для любого m = 0, 1, …, p – 1 существуют 2 состояния,отличимые экспериментом длины m + 1 и не отличимые экспериментом длины m. Следовательно, хотя бы один из классов эквивалентности относительно Rm распадается не менее чемна 2 класса эквивалентности относительно Rm+1. Отсюда1 = s (0) < s (1) < s (2) < … < s (p – 1) < s (p) ≤ r.Так как все s (i) — натуральные числа, то p ≤ r – 1.

Теорема доказана.Следующий пример автомата показывает, что оценку r – 1 в теореме Мура в общем случае улучшить нельзя. Здесь, независимо от входного символа a F(a, qi) = 0, для i = 2, 3, …, r иF(a, q1) = 1.0,100q1q2q310011…0…110qr–1qr0001Для того, чтобы отличить состояния qr–1 и qr надо перевести хотя бы одно из них в q1(входным словом длины r – 2) и затем подать ещё один входной символ. Следовательно, минимальная длина эксперимента, отличающего qr–1 и qr, равна r – 1.Определение 2.

Пусть 2 автомата (A, B, Q1, G1, F1) и (A, B, Q2, G2, F2) имеют одинаковые входной и выходной алфавиты. Пусть qi ∈ Q1 и qj ∈ Q2. Будем говорить, что экспериментa ∈ A∗ отличает состояния qi и qj, если F1 (a , qi ) ≠ F2 (a , q j ).Теорема 4. Пусть даны 2 автомата (A, B, Q1, G1, F1) и (A, B, Q2, G2, F2). Пусть |Q1| = r,|Q2| = m и qi ∈ Q1, qj ∈ Q2. Тогда, если qi и qj отличимы, то существует отличающий их эксперимент a длины l (a ) ≤ r + m − 1 .Доказательство. Можно считать, что Q1 ∩ Q2 = ∅. Рассмотрим автомат (A, B, Q, G, F), вкотором Q = Q1 ∪ Q2 и диаграмма которого получается объединением диаграмм исходныхавтоматов. Тогда |Q| = r + m и по теореме Мура qi, qj отличимы экспериментом a длиныl (a ) ≤ r + m − 1 .

Теорема доказана.43Следующий пример автомата показывает, что оценка r + m – 1 в общем случае не улучшаема. Здесь предполагается m ≥ r и опять выходной символ зависит только от текущего состояния и не зависит от входного символа.q1′0,11q2′0…001qr–1′001…1qr′qr+1′00100…0qm–1′00qm′00111Легко видеть, что если не использовать состояние qm′ второго автомата, то нельзя отличить состояния q1 и q1′ . Поэтому для того, чтобы отличить q1 и q1′ сначала надо перевестивторой автомат словом a из q1′ в q′m .

При этом l (a1 ) ≥ m − 1 и первый автомат под действиемa перейдёт из q1 в qr. Чтобы далее получить различные выходные последовательности, надоперевести первый автомат из qr в q1 и подать ещё один символ. Всего для того, чтобы отличить q1 от q1′ потребуется входное слово длины (m – 1) + (r – 1) + 1 = m + r – 1.44.