Определение реакции автомата на входное слово

Пример 4.5. Определить реакцию автомата на входное слово (последовательность входных символов составляет входное слово; аналогично - для выходного слова)

Пусть на вход автомата Мили А_А и эквивалентного ему автомата Мура А_В из примера 4.3 поступает входное слово . Рассмотрим реакцию автоматов на входное слово.

Для автомата Мили имеем: ; , т.е. под действием символа х₁ автомат переходит в состояние с выходом у₁; при следующем символе получим: ; и т. д. В результате получим последовательность состояний и выходное слово:

входное слово x	-	= k *
cостояния S		= k+1
выходное слово h	-	= k

Для автомата Мура А_В имеем: при вхождении символа х₁ автомат находился в состоянии с выходом , ; . Далее поступает следующий символ х₁ в состоянии с выходом и т.д. Последовательность входных и выходных символов, а также символов состояний выглядит аналогично представленным выше для автомата Мили:

входное слово x	-	= k
cостояния S		= k+1
выходное слово h		= k+1

Видно, что реакция автоматов А_А и А_В на входное слово совпадают с точностью до сдвига на один такт; это получилось потому, что реакция автомата Мура на входную букву наступает в следующем такте. Так будет и в общем случае, если автоматы эквивалентны и разных типов. Проверка этого утверждения предоставляется студентам.