43. Типы конечных автоматов, автоматы Мили и Мура, автоматы-генераторы.

Определение.Конечным автоматом(или автоматом Мили)называется система из пяти компонент (А, В,V,f,g), где А и В – это входной и выходной алфавиты автомата,V– множество его состояний,f– функция выходов, аg– функция переходов автомата, причем все множества А, В иVконечны.

Определение.Любую конечную последовательность символов из входного или выходного алфавитов называются соответственно входным и выходным словом. Множество всех входных слов обозначим через А^*.

Определение.Любое подмножество множества А^*называется языком.

Автоматы-распознаватели, автоматы-преобразователи и автоматы-генераторы – конечные детерминированные автоматы.

Автоматы-распознаватели. Основной особенностью этих автоматов является то, что множество их состоянийVвсегда разбивается на два непересекающихся класса:FиV\F. Все состояния из классаFсчитаются особыми и называются заключительными состояниями. Если на вход такому автомату подать словоw, составленное из символов алфавита А, то может оказаться, что автомат завершит работу в одном из заключительных состояний. В этом случае будем говорить, что автомат распознает данное словоw. Все слова, которые распознает автомат, образуют подмножество множества А^*, т.е. составляют некоторый языкL. Тогда про языкLговорят, что он распознается этим автоматом, или что данный автомат распознает языкL. По­скольку считается, что такой автомат распознает словоwтолько тогда, когда он завершает работу над этим словом в одном из заключитель­ных состояний, то о результате работы автомата мы судим лишь по его состоянию в момент завершения работы. При этом выходные сим­волы, возникающие в процессе функционирования таких автоматов, особого значения не играют. Следовательно, можно игнорировать выходные сигналы или вообще убрать выходной канал. Поэтому автоматы-распознаватели иногда ещё называют автоматами без выходов. Их функционирование можно описать только одной функцией – функцией переходов. Из этого следует, что автомат-распознаватель – это система из четырех компонент : (А,V,F,g), где А – входной алфавит,V– множество всех состояний,F– множество заключительных состояний, аg– функция переходов. В диаграмме Мура такого автомата уже не нужно указывать выходные сигналы, а его таблица выходов и переходов преобразуется в более простую таблицу переходов.

Автоматы-преобразователи.В отличие от авто­матов-распознавателей у них всегда задана функция выходовf. Авто­маты-преобразователи посимвольно прочитывают входную последова­тельность и перерабатывают её в выходную последовательность такой же длины. Например, с их помощью можно моделировать процессы алфавитного кодирования информации. Любой автомат-распознаватель нетрудно превратить в автомат-преобразова­тель. Для этого достаточно считать, что выходной сигнал в конце каж­дого такта совпадает с входным сигналом в начале этого же такта, т.е.y(t) = x(t). Полученный таким образом автомат-преобразователь можно использовать для генерации слов, принадлежащих тому языку, который распознавался исходным автоматом-распознавателем. Когда мы рассматриваем какой-либо конкретный автомат-преоб­разователь, нам в первую очередь важно знать, какая последователь­ность получается на выходе этого автомата при заданной входной по­следовательности. Когда же мы исследуем автомат-распознаватель, нам важно знать лишь состояние, в котором этот автомат закончил работу над заданным словом. Таким образом, автоматы-преобразова­тели лучше подходят для описания вычислительных устройств, а ав­томаты-распознаватели – для описания устройств управления.

Среди автоматов-преобразователей особо выделяют автоматы Мура. Это автоматы, у которых функция выходовfне зависит от входного сигнала, т.е.f(a_i,v_j) = f(a_k,v_j) = b_jВ для всехa_i,a_kА иv_jV. У автомата Мура для каждогоtвыходy(t) может зависеть от состояния автомата в начале этогоt–го такта, т.е. отq(t– 1), но не должен зависеть от входного сигналаx(t). Образно говоря, выходные сигналы автомата Мура зависят от входных сигналов лишь с «запаздыванием».

В отличие от автомата Мили, в диаграмме автомата Мура метка на дуге – это не пара символов a_iиf(a_i,v_j), а только один входной символa_i. При этом символомf(a_i,v_j) помечается сама вершинаv_j. Это объясняется тем, что, согласно определению автомата Мура, выходной символf(a_i,v_j) совпадает у всех дуг, выходящих из одной и той же вершиныv_j. В следующем примере рассматривается простейший автомат Мура, который часто используется в качестве строительного блока для более сложных автоматов.

Автоматы-генераторы.Автономный автомат (автомат-генератор) – это автомат без входа. Он полностью определяется системой из пяти компонент (В,V,F,f,g), где В – выходной алфавит,V– множество всех состояний,F– множество заключительных состояний, аfиg– функции выходов и переходов, причемfиgявляются функциями только одного аргумента – состояния автомата. Генераторы используются, например, для порождения символьных строк в алфавите В. Слово, порожденное автономным автоматом, – это последовательность выходных сигналов, которая образуется при завершении работы автомата в любом из заключительных состояний. Далее мы увидим, что при фиксированном начальном состоянии выходное слово, порожденное генератором, зависит лишь от продолжительности его работы. Меняя начальное состояние и (или) число рабочих тактов, можно породить некоторый язык из В^*, т.е. набор слов в алфавите В.

Логические автоматы.Автоматы, у которых входной и выходной алфавиты и множество состояний образованы наборами из нулей и единиц фиксированной длины. Благодаря этому функции переходов и выходов автоматаfиgможно считать логическими (булевыми) функциями. Схема из функциональных элементов – дизъюнкторов, конъюнкторов и инверторов – это логический автомат без памяти и, следовательно, с одним состоянием. Функциональный блок любого логического автомата можно «синтезировать» из функциональных элементов, а его память – из рассмотренных выше единичных задержек.