Теория автоматов. - 2 стр.

       Теория автоматов относится к числу ключевых разделов современной
кибернетики. Она непосредственно связана с математической логикой, теорией
алгоритмов, теорией формальных грамматик.
       Универсальность и сравнительная простота автоматов обусловили широ-
кое использование автоматных моделей на практике. Теория автоматов, напри-
мер, успешно используется при построении узлов цифровых вычислительных
машин; при построении программ и, в частности, лексических анализаторов в
трансляторах.
       Абстрактная теория автоматов выделяет два основных способа исполь-
зования автоматов: преобразование входной последовательности символов в
выходную (синтез дискретных устройств) и проверка правильности входной по-
следовательности символов (синтез программных анализаторов).
       В данных методических указаниях дана краткая теоретическая справка, а
также приведены примеры синтеза и эквивалентных преобразований автоматов.
Для закрепления знаний приведены упражнения, для некоторых из них даны
решения.
       Структурный синтез автоматов и вопросы их практического использова-
ния будут рассматриваться в последующих курсах, связанных с цифровыми вы-
числительными машинами.


                          ПОНЯТИЕ АВТОМАТА

       Автоматом называют дискретный преобразователь информации, кото-
рый принимает входные сигналы (буквы) в дискретные моменты времени и с
учетом своего прежнего состояния формирует выходные сигналы и изменяет
свое состояние.
       Автомат есть система

                        U=,

где X={x1, x2, …, xn} – входной алфавит;
    Y={y1, y2, …, ym} - выходной алфавит;
    Q={q0 ,q1, …, qs} - алфавит внутренних состояний;
       f (q, x): Q∗X→Q – функция переходов;
       ϕ (q, x):Q∗X→Y – функция выходов.
      Часто фиксируют также начальное состояние автомата q0∈Q. Такие ав-
томаты называют инициальными (будем рассматривать только инициальные
автоматы).
      Законы функционирования автоматов:
      а) для автоматов первого рода (автоматов Мили)
                            q ( t ) = f ( q ( t-1 ), x ( t )),
                            y ( t ) = ϕ ( q ( t-1 ), x ( t ));
      б) для автоматов второго рода
                            q ( t ) = f ( q ( t-1 ), x ( t )),
                             y ( t ) = ϕ ( q ( t ), x ( t ));
      в) для правильных автоматов второго рода (автоматов Мура)
                            q ( t ) = f ( q ( t-1 ), x ( t )),
                                  y ( t ) = ϕ ( q ( t )).