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

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

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

 

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

 

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

, где

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

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

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

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

функция переходов 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. Автомат называют инициальным, если у него задано начальное состояние q0Î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)).

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

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

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

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

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

 

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

 

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

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

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

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

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

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

Функция переходов 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 приведена таблица переходов автомата "Умный родитель". Некоторые сигналы не вызывают изменения состояния, например, под действием х1 автомат сохраняет состояние q2 (рис. 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.

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...