Теория автоматов. Аралбаев Т.З - 25 стр.

       5 Практическое занятие №5. Формы задания конечных автоматов

        Цифровой автомат (ЦА) - это устройство для преобразования дискретных
данных в результате перехода из одного состояния в другое под воздействием
входных сигналов и сохраняющее свое состояние при отсутствии последних.
        Как правило, ЦА описывается следующем кортежем: М = {X, Y, S, δ, λ,
s0}, где X, Y, S – соответственно множества входных, выходных значений и
внутренних состояний ЦА.
        X = {x1, x2, x3, …..xn}; Y = {y1, y2, y3, …..ym}; S = {s1, s2, s3, ……sk}; (5.1)
 где m, n, k – числа элементов множеств;
        δ, λ – соответственно функция перехода из одного состояния в другое и
функция выхода ЦА;
        s0 – начальное состояние ЦА.
        Задать автомат – это значит определить все элементы выражения (5.1).
        Если m, n, k конечны, то автомат называют конечным. Состояние ЦА
определяется состоянием элементов памяти.
        По закону функционирования или по виду выходной функции ЦА делятся
на: автоматы первого рода (автоматы Мили) и автоматы второго рода.
        Модель функционирования автомата Мили имеет следующий вид:
                         s(t)= [s(t-1), x(t)], y(t)= [s(t-1), x(t)],          (5.2)
где:     s(t) - состояние автомата в настоящий момент дискретного времени;
         s(t-1)- состояние автомата в предыдущий момент. Если t=0, то s(t-1)=s0;
         x(t) - входной сигнал в текущий момент;
          - оператор (функция) формирования состояния;
          - оператор (функция) формирования выходного сигнала.
    Таким образом, функционирование ЦА представляется совокупностью двух
функций: функции перехода  и функции выхода . При этом состояние s(t)
зависит от предыдущего состояния s(t-1) и входного сигнала в данный момент
времени, выходной сигнал в данный момент времени так же определяется
предыдущим состоянием и входным сигналом в данный момент времени.
        Закон функционирования ЦА 2-го описывается следующим образом:
                          s(t) = [s(t-1), x(t)], y(t) = [s(t), x(t)].        (5.3)
        Если функцию выхода в последнем выражении представить как:
                                          y(t) = [(s(t)],                     (5.4)
то получим модель работы автомата Мура, являющегося одним из представителей
ЦА 2-го рода.
        Как видно из описаний автоматов, у ЦА Мили выходной сигнал имеется
только тогда, когда есть входной сигнал, а у ЦА Мура выходной сигнал на
текущий момент не зависит от входного сигнала.
        Большинство аппаратно-программных средств вычислительной техники
описывается автоматами Мили и Мура.
        Для описания (задания) ЦА используются разнообразные средства,
называемые языками, которые делятся на начальные и автоматные языки.
        Среди начальных языков основными являются: язык логических

                                                                                    25