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

Таким образом, для каждой и каждого символа имеется единственное ребро

выходит ребер, помеченных парами символов .

состояние q0 и из каждой вершины

ориентированный (мульти) граф DA=(Q, E) с помеченными ребрами, в котором выделена вершина- начальное

размеченных графов.Определение 4.2. Диаграмма автомата - это

а столбцы - символам из входного алфавита . В первой из них на пересечении строки qi и столбца aj стоит состояние , а во второй - выходной символ .Еще один способ представления конечного автомата основан на использовании ориентированных

(матрицей) размера n x m, строки которой соответствуют состояниям из Q,

Каждая из них определяется таблицей

список из m n команд вида .Другой удобный способ задания функций и - табличный.

в темпе ее поступления. АвтоматНа такие устройства в последовательные дискретные моменты времени 1,2, ..., t, t+1,... поступают входные сигналы x(1),x(2), ..., x(t),x(t+1),... и в ответ на них автомат A вырабатывает выходные сигналы y(1) y(2), ..., y(t), y(t+1),.... Конечные автоматы характеризуются двумя особенностями.Отсутствие предвосхищения: выходной сигнал y(t), выдаваемый автоматом в момент t, зависит лишь от полученных к этому времени входов x(1),x(2), ..., x(t), т.е. автомат не может предвосхитить будущие входы и заранее на них отреагировать. Таким образом, имеется некоторая функция выходов , определяющая очередной выход по предшествующему входу.Конечная память: в каждый момент t информация в автомате о полученном к этому моменту входе x(1),x(2), ..., x(t) конечна. Это свойство удобно интерпретировать следующим образом: автомат имеет конечное множество состояний Q и в каждый момент находится в одном из этих состояний. При получении очередного входа состояние может измениться. Таким образом, состояние , в котором находится автомат после получения входной последовательности x(1),x(2), ..., x(t), и представляет информацию об этой последовательности, используемую в дальнейшей работе автомата при определении следующего состояния и выхода.Наше обсуждение приводит к следующему определению конечного автомата с выходом.Определение 4.1. Конечный автомат - преобразователь - это система видавключающая следующие компоненты: - конечное множество - входной алфавит ; - конечное множество - выходной алфавит ;Q={q0, ... , qn-1} (n >= 1) - конечное множество - алфавит внутренних состояний; - начальное состояние автомата; - функция переходов, - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a ; - функция выходов, - это символ из , который выдает на выход автомат в состоянии q, когда получает на вход символ a.Иногда пару функций называют программой автомата A и задают как

перерабатывающих дискретную входную информацию в режиме "реального времени", т.е.

Переработка информации с помощью конечных автоматовКонечные автоматы являются математической моделью устройств,

относительно теоретико-множественных операций

правильности автомата. Произведение автоматов. Замкнутость класса конечно-автоматных языков

Конечные автоматы-распознаватели. Конечно-автоматные языки. Доказательство

Конечные автоматы-преобразователи. Пример: сложение двоичных чисел.

Конечные автоматы: преобразователи и распознаватели: версия для печати и PDA

Введение в схемы, автоматы и алгоритмы

Интернет-Университет Информационных Технологий

INTUIT.ru::Интернет-Университет Информационных Технологий