- •Определения и способы описания конечных автоматов
- •Математическая модель и схема рекуррентных соотношений конечного автомата "Умный родитель"*)
- •Графический способ описания конечного автомата "Умный родитель"
- •Табличный способ описания конечного автомата "Умный родитель"
- •Реализация конечного автомата "Умный родитель" в среде электронных таблиц ms Excel
Определения и способы описания конечных автоматов
1. Абстрактный автомат – математическая модель реальных динамических систем. Области применения абстрактных автоматов: схемотехника (синтез схем вычислительных устройств), бытовая и промышленная автоматика, устройства и системы управления, распознавание формальных языков.
2. Для работы автомата характерна дискретность изменения состояния системы: все переменные изменяются в дискретные моменты времени – такты. Целочисленная переменная – номер такта,. Текущее состояние конечного в момент, последующее – в момент (+1). Автомат – система переработки, отображения входной информации в выходную.
3. Конечный абстрактный автомат определяется набором характеристик:
, где
– входной алфавит,n - число символов входного алфавита конечно,
– выходной алфавит,m -число символов выходного алфавита конечно,
– алфавит состояний автомата, l- число символов алфавита состояний автомата, конечно,
q0– начальное состояние автомата,
функция переходов (+1)=(x(),q()) реализует отображение,
функция выхода ()=(x(),q())реализует отображение.
4. По способу формирования функций выхода выделяют автоматы Мили и Мура.
4.1. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата.
4.2. В автомате Мура функция выхода определяет значение выходного символа только по одному аргументу - состоянию автомата, т.е. символ y()в выходном канале существует, все время пока автомат находится в состоянииq().
Для автомата Мура функция выхода записывается в виде: ()=( q()),
реализует отображение .
5. Автомат называют инициальным, если у него задано начальное состояние q0Q, в котором он находится всегда до приема первого символа входного слова. В этом случае модель автомата записывают так:
.
6. Автомат называют детерминированным, если для каждой пары (q; x)QX)функции переходов и выходов однозначно определены. В противном случае автомат называют недетерминированным или частично определенным.
7. Способ описания конечного автомата определяется способом задания функций () и().
Аналитический способописания конечного автомата: определение алфавитов входных сигналов (X) и выходных сигналов (Y), множества состояний (Q), функции переходов и выходов задаются каноническими уравнениями (аналитическое задание функций)(+1)=(x(),q()),()=(x(),q()).
Графический способописания конечного автомата – определение диаграммы переходов автомата. Диаграмму переходов называют графом автомата или графом переходов автомата. Граф автомата - орграф, вершины которого соответствуют состояниям, а дуги - переходам между ними. Вершиныqiиqjсоединены дугой, если, дуге приписывается входной сигнал xmXи выходной сигналynY. матрица соединений автомата – квадратная матрица, в которой строки соответствуют исходным состояниям, столбцы – состояниям перехода, элемент матрицы содержит два символа: входной символ, который связывает эти два состояния, и выходной символy=(x(),q()).
При табличном способеописания конечного автомата
определяются алфавиты входных (X) и выходных (Y) сигналов, алфавит состояний (Q).
значения функций переходов () и выходов()задаются таблицами.
Для программной реализации конечного автомата удобнее использовать совмещенную таблицу переходов и выходовиликодированную таблицу переходов и выходов.