Спирина, М.С. Дискретная математика

подходе /(Го) — число таких изменений, произошедших до мо­ мента времени Г0. Примером дискретизации служит обычный ки ­ нематограф: время разбито на интервалы длительностью 1/(24 с), и человеческий глаз воспринимает следование дискретных кадров как непрерывное движение. В зависимости от способа организации функции выхода синхрон­ ные автоматы делятся на автоматы Мили и автоматы Мура. В автоматах Мили (автоматы I рода) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t - 1) автомата в предшествующий момент времени ( / - 1). Мате­ матической моделью таких автоматов служит система уравнений: J <?(/) = § ( ? ( / - 1 ), х(/)), |у ( / ) = А.(^(/-1), х(/)), В автоматах Мура (автоматы II рода) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени /. Математической моделью таких \q{t) = b (q ( t- \) , *(/)), автоматов является система: ( ЫО = Чя(0)- В таких автоматах функция выхода зависит только от состояний автомата в данный момент времени и не зависит от входного сиг­ нала. Таким образом, входная строка такого автомата однократно считывается слева направо, осуществляя поочередный просмотр символов. В определенный момент времени конечный автомат на­ ходится в некотором внутреннем состоянии, которое изменяется после считывания очередного символа. Новое состояние можно охарактеризовать считанным символом и текущим состоянием. Комбинационными называются автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущи­ ми входными символами, т. е. в этом автомате все состояния эк ­ вивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неиз­ менна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние. Кроме комбинационных, существуют также и логические авто­ маты, у которых входной алфавит состоит из 2т двоичных набо­ ров длины т, а выходной — из 2ядвоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных. Представление событий в автомате. Обозначим через X* мно­ жество входных слов автомата Z, составленное из множества букв входного алфавита X. Множества слов входного алфавита называ­ ют также событием или языком. Для некоторого автомата Z определим функции перехода Sz и выхода Х2 индуктивно : 346