Главная | Обратная связь | Поможем написать вашу работу!

Определения и способы описания конечных автоматов

1. Абстрактный автомат – математическая модель реальных динамических систем. Области применения абстрактных автоматов: схемотехника (синтез схем вычислительных устройств), бытовая и промышленная автоматика, устройства и системы управления, распознавание формальных языков.

2. Для работы автомата характерна дискретность изменения состояния системы: все переменные изменяются в дискретные моменты времени – такты. Целочисленная переменная t – номер такта, . Текущее состояние конечного в момент t, последующее – в момент (t +1). Автомат – система переработки, отображения входной информации в выходную.

3. Конечный абстрактный автомат определяется набором характеристик:

, где

– входной алфавит, n - число символов входного алфавита конечно,

– выходной алфавит, m -число символов выходного алфавита конечно,

– алфавит состояний автомата, l - число символов алфавита состояний автомата, конечно,

q₀ – начальное состояние автомата,

функция переходов Y(t+1)=Y(x(t),q(t)) реализует отображение ,

функция выхода Q(t)=Q(x(t),q(t)) реализует отображение .

4. По способу формирования функций выхода выделяют автоматы Мили и Мура.

4.1. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата.

4.2. В автомате Мура функция выхода определяет значение выходного символа только по одному аргументу - состоянию автомата, т.е. символ y(t) в выходном канале существует, все время пока автомат находится в состоянии q(t).

Для автомата Мура функция выхода записывается в виде: Q(t)=Q(q(t)),

реализует отображение .

5. Автомат называют инициальным, если у него задано начальное состояние q₀ÎQ, в котором он находится всегда до приема первого символа входного слова. В этом случае модель автомата записывают так:

6. Автомат называют детерминированным, если для каждой пары (q; x)Î(QÄX) функции переходов и выходов однозначно определены. В противном случае автомат называют недетерминированным или частично определенным.

7. Способ описания конечного автомата определяется способом задания функций Y(t) и Q(t).

Аналитический способ описания конечного автомата: определение алфавитов входных сигналов (X) и выходных сигналов (Y), множества состояний (Q), функции переходов и выходов задаются каноническими уравнениями (аналитическое задание функций) Y(t+1)=Y(x(t),q(t)), Q(t)=Q(x(t),q(t)).

Графический способ описания конечного автомата – определение диаграммы переходов автомата. Диаграмму переходов называют графом автомата или графом переходов автомата. Граф автомата - орграф, вершины которого соответствуют состояниям, а дуги - переходам между ними. Вершины q_i и q_j соединены дугой, если , дуге приписывается входной сигнал x_mÎX и выходной сигнал y_nÎY. матрица соединений автомата – квадратная матрица, в которой строки соответствуют исходным состояниям, столбцы – состояниям перехода, элемент матрицы содержит два символа: входной символ, который связывает эти два состояния, и выходной символ y=Y(x(t),q(t)).

При табличном способе описания конечного автомата

- определяются алфавиты входных (X) и выходных (Y) сигналов, алфавит состояний (Q).

- значения функций переходов Y(t) и выходов Q(t) задаются таблицами.

Для программной реализации конечного автомата удобнее использовать совмещенную таблицу переходов и выходов или кодированную таблицу переходов и выходов.

Математическая модель и схема рекуррентных соотношений
конечного автомата "Умный родитель"^*)

Конечный автомат «Умный родитель» определяется набором характеристик:

«Умный родитель» ,

Входной алфавит: = { неудовлетворительно, отлично }.

Выходной алфавит: = { брать ремень, ругать ребенка, успокаивать ребенка, надеяться, радоваться, ликовать }.

Алфавит состояний автомата: = { начальное состояние, расстроенное,
гневное, радостное }.

q_{0 =} начальное состояние – начальное состояние автомата, т.е. автомат инициальный.

Функция переходов Y(t+1)=Y(x(t),q(t)) реализует отображение .

Функция выхода Q(t)=Q(x(t),q(t)) реализует отображение .

^*)Карпов Юрий Глебович. Теория автоматов: Учеб. Для вузов.- СПб.: Питер, 2003.- 208 с.: ил.

^*)Пак Н.И. Информатика: учеб. пособие/ Н.И.Пак; Краснояр.гос.ун-т – Красноярск, 2006

Графический способ описания конечного автомата "Умный родитель"

Алгоритм работы конечного автомата описывается с помощью орграфа.

Вершины графа автомата соответствуют состояниям: , а дуги – переходам между ними. Дуге приписываются входной и выходной символы (рис. 1).

Граф автомата описывается матрицей соединений, в которой строка соответствует текущему состоянию (в момент времени – t), столбец – последующему (в момент времени – (t+1)). Элемент матрицы содержит два символа: входной символ (x(t)), который связывает эти два состояния, и выходной символ y=Y(x(t),q(t)).

Матрица соединений, приведенная на рис. 2, соответствует графу автомата "Умный родитель" (рис. 1).

Табличный способ описания конечного автомата "Умный родитель"

Табличный способ описания автомата Мили предполагает наличие таблицы переходов (рис.3) и таблицы выходов (рис. 4).

В таблице переходов в первой строке записываются элементы алфавита состояний автомата: , а элементы входного алфавита (входные сигналы) — в первом столбце. На пересечении строк и столбцов записывается состояние автомата в следующий момент времени. Таблица переходов может быть определена не полностью, в таких случаях в соответствующей клетке записывают прочерк.

На рис. 3 приведена таблица переходов автомата "Умный родитель". Некоторые сигналы не вызывают изменения состояния, например, под действием х₁ автомат сохраняет состояние q₂ (рис. 3).

Рис. 3. Таблица переходов автомата "Умный родитель"

В таблице выходов возможные состояния тоже записываются в первой строке, а входные сигналы — в первом столбце. Эта таблица также может быть не полностью определенной. На пересечении соответствующих строки и столбца записывается выходной сигнал автомата.

На рис. 4 приведена таблица выходов автомата "Умный родитель".

Рис. 4. Таблица выходов автомата "Умный родитель"

Обе таблицы (таблицу переходов и таблицу выходов) можно совместить, в таком случае на пересечении соответствующих строки и столбца записывается пара значений: состояние автомата в следующий момент времени и выходной сигнал автомата. На рис.5 приведена совместная таблица переходов и выходов автомата "Умный родитель".

Рис. 5. Совместная таблица переходов и выходов

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

Реализация конечного автомата "Умный родитель" в среде электронных таблиц MS Excel

1. Закодировать равномерным двоичным кодом символы входного алфавита автомата "Умный родитель" и записать их в справочник, для этого: 1.1. Определить длину кодового слова равномерного двоичного кода для символов входного алфавита: = { неудовлетворительно, отлично }. Воспользоваться формулой: (бит). 1.2. Кодовые слова символов записать справочник на рабочем листе MS Excel, ключевое поле справочника – входной символ алфавита. Кодовые символы разместить в ячейках диапазона C5:C6 (рис.6).
2. Закодировать равномерным двоичным кодом символы выходного алфавита автомата "Умный родитель" и записать их в справочник, для этого: 2.1. Определить длину кодового слова равномерного двоичного кода для символов выходного алфавита: = { брать ремень, ругать ребенка, успокаивать ребенка, надеяться, радоваться, ликовать }. Воспользоваться формулой: (бита). 2.2. Кодовые слова символов выходного алфавита записать в справочник на рабочем листе MS Excel, ключевое поле справочника – кодовое слово символа выходного алфавита. Кодовые слова разместить в ячейках диапазона Е5:Е10 (рис.7). 2.3. Символы выходного алфавита разместить в ячейках диапазона F5:F10. Рис. 7. Справочники кодовых слов для символов входного и выходного алфавитов
3. Закодировать равномерным двоичным кодом символы алфавита состояний автомата "Умный родитель" и записать их в справочник, для этого: 3.1. Определить длину кодового слова равномерного двоичного кода для символов алфавита состояний автомата: = { начальное состояние, расстроенное, гневное, радостное }. Воспользоваться формулой: (бита). 3.2. Кодовые слова символов алфавита состояний записать справочник на рабочем листе MS Excel, ключевое поле справочника – кодовое слово символа выходного алфавита. Кодовые слова разместить в ячейках диапазона I5:I8 (рис.8). 3.3. Символы выходного алфавита разместить в ячейках диапазона J5:J10 (рис. 8). Рис. 8. Справочники кодовых слов для символов входного, выходного алфавитов и алфавита состояний
4. Для формирования кодированной таблицы переходов и выходов необходимо создать совместную таблицу переходов и выходов в ячейках рабочего листа D15:H21. В клетки таблицы записать кодовые слова для символов входного, выходного алфавитов и алфавита состояний как показано на схеме (рис. 9). Рис. 9. Совместная таблица значений функций переходов и выходов
5. По данным совместной таблицы переходов и выходов составить кодированную таблицу переходов и выходов (рис.10). Это справочник, его строка состоит из трех полей: – ключевого поля, – кодового слова, определяющего состояние автомата в следующий момент времени, – кодового слова, определяющего выходной символ алфавита. Таблицу разместить в диапазоне N3:P10 рабочего листа, заполняя построчно значения ячеек: а) ключевое поле справочника (значения в ячейках колонки N) формируется из трех двоичных символов: первый бит – кодовый знак символа входного алфавита, адресует строку совместной таблицы переходов и выходов, два следующих бита – кодовый знак символа алфавита состояний, адресует колонку совместной таблицы переходов и выходов, б) клетка совместной таблицы переходов и выходов, которая расположена на пересечении этой строки и столбца (рис.9), содержит кодовое слово последующего состояния. Записать его в поле кодовой таблицы «Последующее состояние», в) кроме того, в этой же клетке совместной таблицы переходов и выходов записано кодовое слово выходного символа. Занести это кодовое слово в поле кодовой таблицы «Выходной символ». Рис. 10. Кодированная таблицы переходов и выходов на рабочем листе MS Excel
6. «Кодированная таблица переходов и выходов» – служит справочником. Поэтому строки этой таблицы следует упорядочить по возрастанию значения поля «Входной символ/Текущее состояние».

7. Подготовить диапазон ячеек A28:F29 для демонстрации работы автомата "Умный родитель": 7.1. Занести наименования столбцов в ячейки диапазона A28:F28 в соответствии со схемой на рис. 11. 7.2. В ячейку С29 занести код начального состояния – "00". 7.3. Из справочника «Входной алфавит X» в ячейку D29 выбрать соответствующий этому коду символ входного алфавита (рис. 11), для этого в ячейку D29 ввести формулу: =ВПР(C29;$I$5:$K$8;2) Диапазон ячеек примет вид

Рис. 11. Подготовка к демонстрации работы автомата

8. Диапазон ячеек А30:F30 соответствует первому такту работы автомата. Для определения кодов и символов входного, выходного алфавита и алфавита состояний для первого такта использовать следующие формулы: 8.1. В ячейку B30 ввести формулу определения кода входного символа: =ВПР(A30;$A$5:$C$6;3) 8.2. В ячейку C30 ввести формулу: =ВПР(B30&C29;$N$3:$P$10;2). Эта формула определяет код состояния автомата на первом такте работы автомата. Первый параметр функции задает образец поиска в кодированной таблице переходов и выходов. Образец состоит из трех битов: первый бит – кодовый знак символа входного алфавита, значение ячейки B30, два следующих бита – код начального состояния, значение ячейки C29. 8.3. В ячейку D30 ввести формулу: =ВПР(C30;$I$5:$K$8;2). 8.4. В ячейку E30 ввести формулу: =ВПР(B30&C29;$N$3:$P$10;3). 8.5. В ячейку F30 ввести формулу: =ВПР(E30;$E$5:$G$10;2).

9. Чтобы убедиться в корректности введенных формул, измените режим просмотра рабочего листа. На линейке управления перейдите на закладку Формулы, затем активируйте команду Показать формулы (рис. 12).

Рис.12. Переход в режим просмотра формул рабочего листа

10. Включается режим просмотра формул в ячейках рабочего листа (рис.13).

Рис.13. Просмотр рабочего листа в режиме формул

11. Просмотрите формулы и вернитесь в режим отображения значений результата (рис. 14).

Рис. 14. Просмотр рабочего листа в режиме отображения результата.

12. В диапазон ячеек B30:B35 ввести входную цепочку символов (рис. 15), например, такую: неудовлетворительно отлично отлично неудовлетворительно отлично отлично

Рис. 15. Входная цепочка символов автомата "Умный родитель" записывается в диапазон B30:B35

13. Определить значения ячеек диапазона для каждого входного символа. Для этого выделить диапазон ячеек B30:F30 и маркером автозаполнения раскопировать его на диапазон B30:F35 (рис. 16).

Рис. 16. Диапазон ячеек рабочего листа MS Excel – иллюстрация работы автомата "Умный родитель"

14. Схема рабочего листа со сценарием работы автомата "Умный родитель" представлена на рис. 17.

Рис. 17. Рабочий лист MS Excel – результат выполнения лабораторной работы 4.