Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Эта схема является искомой. Теорема доказана.

§38. Теорема Мура. Теорема об отличимости состояний двух автоматов

Будем рассматривать автоматы, в которых не выделено начальное состояние, то есть автомат задаётся пятёркой (A, B, Q, G, F).

Через A^* будем обозначать множество всех конечных слов в алфавите A. Расширим функции F и G, определив и для любого состояния q_i  Q и любого слова . Пусть автомат (A, B, Q, G, F) находится в состоянии q_i  Q и на вход подаётся слово . Тогда на выходе будет последовательно выдаваться некоторое слово и после подачи всего слова автомат окажется в некотором состоянии q_k. Расширим функции F и G, положив , .

Определение 1. Два состояния q_i и q_j автомата (A, B, Q, G, F) называются отличимыми, если существует входное слово такое, что . При этом слово называют экспериментом, отличающим q_i и q_j, а длину — длиной этого эксперимента.

Лемма. Пусть в автомате (A, B, Q, G, F) есть 2 состояния q_u и q_v, отличимые экспериментом длины p и не отличимые более коротким экспериментом. Тогда для любого k, где 1  k  p, существуют 2 состояния, отличимые экспериментом длины k и не отличимые более коротким экспериментом.

Доказательство. Пусть состояния q_u, q_v отличимы экспериментом длины p и не отличимы экспериментом меньшей длины. Пусть . Тогда , причём и различаются только последней буквой. Разобьём все слова , , на 2 подслова , , , где . Пусть , . Тогда , . Так как и различаются последней буквой, то q' и q'' отличимы экспериментом длины . Допустим, что q' и q'' отличимы экспериментом длины . Тогда , и . Но тогда и . Следовательно, q_u и q_v отличимы экспериментом длины . Это противоречит условию. Значит (от противного), q' и q'' не отличимы экспериментом длины меньшей, чем k. Лемма доказана.

Теорема 3 (Теорема Мура). Если в автомате (A, B, Q, G, F) состояния q_i и q_j отличимы и |Q| = r, то существует эксперимент , отличающий q_i и q_j, длины .

Доказательство. Пусть состояния q_i и q_j отличимы экспериментом длины p и не отличимы более коротким экспериментом. Рассмотрим в данном автомате следующее отношение R_m на множестве состояний Q (m = 0, 1, …, p): состояния q_i и q_j не отличимы экспериментом длины m (считаем, что любые 2 состояния не отличимы экспериментом длины 0). Если для любого слова длины m и , то , поэтому R_m — это отношение эквивалентности для каждого m = 0, 1, …, p. Относительно R_m Q разбивается на классы эквивалентности , так что любые два состояния из одного класса не отличимы экспериментом длины m, а любые два состояния из разных классов отличимы экспериментом длины m. При этом s(0) = 1 и . Посмотрим, как меняются эти классы при переходе от m к m + 1. Если 2 состояния отличимы экспериментом длины m, то они отличимы и экспериментом длины m + 1, поэтому состояния из разных классов остаются в разных классах. По лемме для любого m = 0, 1, …, p – 1 существуют 2 состояния, отличимые экспериментом длины m + 1 и не отличимые экспериментом длины m. Следовательно, хотя бы один из классов эквивалентности относительно R_m распадается не менее чем на 2 класса эквивалентности относительно R_m+1. Отсюда

1 = s (0) < s (1) < s (2) < … < s (p – 1) < s (p)  r.

Так как все s (i) — натуральные числа, то p  r – 1. Теорема доказана.

Следующий пример автомата показывает, что оценку r – 1 в теореме Мура в общем случае улучшить нельзя. Здесь, независимо от входного символа a F(a, q_i) = 0, для i = 2, 3, …, r и F(a, q₁) = 1.

Для того, чтобы отличить состояния q_r–1 и q_r надо перевести хотя бы одно из них в q₁ (входным словом длины r – 2) и затем подать ещё один входной символ. Следовательно, минимальная длина эксперимента, отличающего q_r–1 и q_r, равна r – 1.

Определение 2. Пусть 2 автомата (A, B, Q₁, G₁, F₁) и (A, B, Q₂, G₂, F₂) имеют одинаковые входной и выходной алфавиты. Пусть q_i  Q₁ и
q_j  Q₂. Будем говорить, что эксперимент отличает состояния q_i и q_j, если .

Теорема 4. Пусть даны 2 автомата (A, B, Q₁, G₁, F₁) и (A, B, Q₂, G₂, F₂). Пусть |Q₁| = r, |Q₂| = m и q_i  Q₁, q_j  Q₂. Тогда, если q_i и q_j отличимы, то существует отличающий их эксперимент длины .

Доказательство. Можно считать, что Q₁  Q₂ = . Рассмотрим автомат (A, B, Q, G, F), в котором Q = Q₁  Q₂ и диаграмма которого получается объединением диаграмм исходных автоматов. Тогда |Q| = r + m и по теореме Мура q_i, q_j отличимы экспериментом длины . Теорема доказана.

Следующий пример автомата показывает, что оценка r + m – 1 в общем случае не улучшаема. Здесь предполагается m  r и опять выходной символ зависит только от текущего состояния и не зависит от входного символа.

Легко видеть, что если не использовать состояние второго автомата, то нельзя отличить состояния q₁ и . Поэтому для того, чтобы отличить q₁ и q₁ сначала надо перевести второй автомат словом из в . При этом и первый автомат под действием перейдёт из q₁ в q_r. Чтобы далее получить различные выходные последовательности, надо перевести первый автомат из q_r в q₁ и подать ещё один символ. Всего для того, чтобы отличить q₁ от потребуется входное слово длины (m – 1) + (r – 1) + 1 = m + r – 1.

79

Характеристики

Список файлов лекций