4.2.3. Периодичность выходной последовательности конечного автомата

Оказывается, любой конечный автомат перерабатывает периодическую входную последовательность в периодическую выходную, период которой не превышает где – период выходной последовательности, а – количество состояний автомата. Доказательство этого факта основывается на следующем простом замечании: если входная последовательность имеет период а последовательность состояний автомата – период то выходная последовательность будет иметь период НОК где НОК обозначает наименьшее общее кратное.

Теорема. Если входная последовательность конечного автомата является периодической, то выходная последовательность также периодическая.

4.2.4. Теоремы Мура

Отличимость состояний конечного автомата устанавливают обычно с помощью тестирования. А именно, если автомат, находясь в состоянии и находясь в состоянии будет по-разному реагировать на одну и ту же входную последовательность, то состояния и отличимы. Если на данную тестовую последовательность ответ будет одинаковым (т.е. то можно либо удлинить входную последовательность, добавив элементы либо сменить входную последовательность, заменив её на и т.д. Таким способом можно будет установить отличимость состояний и (если они действительно отличимы), но неотличимость этот способ доказать не позволит, так как невозможно перебрать бесконечное множество последовательностей. Естественно возникает вопрос: сколько тестовых последовательностей и каких достаточно для установления неотличимости двух состояний? Ответ лаёт первая теорема Мура: если – количество состояний автомата, то для установления отличимости или неотличимости его состояний достаточно подавать на вход последовательности длины Для двух автоматов и имеющих одинаковые входные и одинаковые выходные алфавиты, справедлива вторая теорема Мура: для отличимости или неотличимости состояний и этих автоматов достаточно ограничиться входными последовательностями длины где и количества состояний автоматов и

Для дальнейшего нам понадобится ввести некоторые определения и обозначения. Если – входной алфавит, то, как обычно, – множество всех слов (произвольной длины) с буквами из Для пусть обозначает длину слова т.е. количество входящих в него букв. Определим произведение двух подмножеств множества положив

В частности, – множество всех слов длины Очевидно, при (при этом считаем, что где – пустое слово).

Пусть – подмножество множества Будем говорить, что состояния автомата отличимы множеством если существует непустое слово такое, что Если же, наоборот, для всех непустых то и неотличимы множеством Заметим, что из неотличимости состояний и следует их неотличимость множеством для любого Обратно, если отличимы каким-либо множеством то и отличимы.

Для автоматов и с одинаковыми входными и выходными алфавитами аналогичным образом вводятся понятия отличимости (неотличимости) состояний и а также отличимость (неотличимость) множеством

Пусть – конечный автомат. Для подмножества обозначим через отношение неотличимости с помощью т.е. в случае, когда и неотличимы с помощью Ясно, что отношение эквивалентности. Обычная неотличимость – это неотличимость с помощью т.е. Очевидно, т.е. разбиение множества определяемое отношением это измельчение разбиения, определяемого (каждый -класс является объединением одного или нескольких -классов). Итак, наиболее мелким (дробным) из рассматриваемых разбиений является Доказательства теорем Мура будут основываются на двух леммах.

Лемма 1. Пусть и Если то неотличимость состояний равносильна их неотличимости с помощью множества (Другими словами, при выполнении условий леммы мы имеем равенство

Лемма 2. Пусть и Тогда существует такое что

Замечание. Ранее было отмечено, что осуществляет наиболее мелкое разбиение множества Следовательно, если в цепочке в каком-нибудь месте будет иметь место равенство: то все остальные включения также будут равенствами:

Первая теорема Мура. Если состояния автомата отличимы, то они отличимы словом длины где То есть существует такое что

Вторая теорема Мура. Пусть и два автомата с одними и теми же входным и выходным алфавитами. Состояния и являются отличимыми в том и только том случае, если они отличимы множеством где

Доказательство второй теоремы Мура проводится сведением её к первой теореме. Будем считать, что Построим новый автомат полагая

Рассмотрим любые состояния и Если эти состояния отличимы как состояния автоматов и то они отличимы и как состояния автомата Применив к этому автомату первую теорему Мура, получим, что и отличимы множеством (поскольку Таким образом, при некотором Но это означает, что

Приведём теперь пример, показывающий, что для установления отличимости состояний автомата с может оказаться недостаточно брать последовательности длины т.е. число в формулировке первой теоремы Мура не может быть уменьшено.

Пример. Рассмотрим автомат, представленный следующей таблицей:

				…
0	1	0	0	…	0	0
1	1	0	0	…	0	0

Состояния и отличимы словом Действительно, а В то же время слова длины эти состояния не отличают, так как если то