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

Классификацию автоматов можно проводить и по другим о с ­ нованиям. Если в основании классификации лежит объем памяти, то раз­ личие заключается в том, имеет ли автомат конечное или беско­ нечное число внутренних состояний. Под бесконечным автоматом обычно понимают определенную математическую идеализацию представлений об автомате, имею­ щую бесконечное число состояний. Память такого автомата п о ­ тенциально может неограниченно возрастать. Например, извест­ ные абстрактные автоматы Поста и Тьюринга являются бесконеч­ ными автоматами, но сама ЭВМ или ее отдельные части — конечными автоматами. Если в основании классификации лежит механизм случайного выбора, то различают детерминированные и вероятностные (сто­ хастические) автоматы. В детерминированных автоматах поведение и структура в каждый момент времени однозначно определены текущей входной информацией и состоянием самого автомата в предшествующий момент времени. В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором. Вероятностный автомат — это дискретный преобразователь информации, функционирование которого в каждый момент времени зависит только от состояний памяти и описывается статистическими законами. В теории автоматов доказано, что для выполнения различных преобразований информации достаточно построить универсальный автомат с помощью программы и соответствующего кодирова­ ния, способный решать любые задачи. Пусть имеется цифровой автомат с одним входом, математи­ ческая модель которого задается пятью объектами: • X — конечное множество входных символов, входной алфа­ вит: X = (xt(/), x2(t), ..., х„(/)}; множество слов над X - А*; • Y — конечное множество выходных символов, выходной ал ­ фавит: Y= {yi(t), У2(0 , У*(ОН • Q — конечное множество состояний автомата: Q= {qo(t), q\{t), ..., < 7 j( 0 h где q0 — его начальное состояние; • 8(q, х) — функция перехода автомата из одного состояния в другое: Q х X -> Q\ • X(q, х) — функция выхода автомата: Q х X -э К Таким образом, конечный автомат Z={X, Q, Y, 8 , X) определя­ ется рекуррентными соотношениями ?(0) = q0, q(t + 1) = 8 x(t)), y( t ) = X(q(t), x(t)). Здесь t — дискретизированный момент времени, т. е. образ м о ­ нотонной функции Г. Т -> N, где Т — обычное непрерывное вре­ мя, N — множество натуральных чисел. Таким образом, все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При таком 345