Конечный автомат способы задания

Способы задания конечных автоматов

Представление конечного автомата фактически сводится к описанию задающих его автоматных функций. [8]

Существуют три способа задания конечных автоматов:

· Табличный (матрицы переходов и выходов);

· Графический (с помощью графов);

· Аналитический (с помощью формул).

Аналитический способ – автомат задаетсясистемой уравнений. Из такой системы следует, что при конечном числе возможных внутренних состояний количество возможных значений автоматных функций также оказывается конечным. Примером такого задания служат системы уравнений, задающие автоматы Мили и автоматы Мура

Табличный способ.Составляется таблица состояния автоматадля функции перехода – δ и функции выхода. При этом:

· столбцы таблицы соответствуют элементам входного алфавита X,

· строки таблицы соответствуют состояни­ям (элементы конечного множества Q).

Пересечению i-и строки и j-го столбца соответствует клетка (i, j), которая является аргументом функций 8 и λ автомата в момент, когда он находится в состоя­нии q_i на его входе – слово x_j, а в самой соответствующей клетке запишем значения функций 8 и λ. Таким образом, вся таблица соответствует множеству Q х X.

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

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

В матрице переходов на пересечении строки x_k и столбца q_r помещается значение функции перехода δ(q_i, х) и функции выводов λ(q, х). В ряде случаев обе таблицы объединяются в одну таблицу.

Графический способ.

Автомат задается с помощью графа, схемы, графика и др. Задание с помощью ориентированного гра­фа – более удобная и компактная форма описания автомата.

Граф автомата содержит

· Вершины, соответствующие состоянию q_iÎQ,

· Дуги, соединяющие вершины – переходы автомата из одного состояния в другое. На дугах принято указывать пары вход­ных и выходных сигналов – сигналов переходов.

Если автомат переходит из состояния q₁ в состояние q₂ под воз­действием нескольких входных сигналов, то на соответствующей дуге графа этот вариант будет представлен через дизъюнкцию. Для представления автомата используют двухполюсные графы с выде­ленными начальным и конечным состояниями.

Разработка шкалы «прибора для измерения емкости»

№	индикация	+	—	перегруз.	выкл.	┤
0	исх.сост.	1	0	0	0	нет
1	0	2	0	13	0	да
2	50	3	1	13	0	да
3	100	4	2	13	0	да
4	150	5	3	13	0	да
5	200	6	4	13	0	да
6	250	7	5	13	0	да
7	300	8	6	13	0	да
8	350	9	7	13	0	да
9	400	10	8	13	0	да
10	450	11	9	13	0	да
11	500	13	10	13	0	да
12	ОВ	0	0	0	0	нет
13	авария	0	0	0	0	нет

Рис.2.5. Граф шкалы прибора для измерения емкости

Заключение

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

В теоретической части данной курсовой работы были рассмотрены элементы генераторов LC-типа. Также была рассмотрена классификация генераторов LC-типа, их назначение, а также различные схемы генераторов. А также технические характеристики элементов генераторов.

В практической части была раскрыта тема, касающаяся шифраторов, дешифраторов, их назначения, а также были спроектированы электрические функциональные и электрические принципиальные схемы шифраторов и дешифраторов. Была раскрыта тема карт Карно. Также был разработан сегмент “b” семисегментного индикатора. Был разработан конечный автомат для шкалы прибора для измерения емкости, а также граф для него.

Дата добавления: 2018-02-18 ; просмотров: 2766 ; Мы поможем в написании вашей работы!

Источник

Способы задания автомата (Лекция)

1. Табличный способ

2. Графический способ задания автомата

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l . При этом среди множества A = 0,a₁,…, a_n > необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Строки этих таблиц соответствуют входным сигналам x ( t ), а столбцы – состояниям. На пересечении столбца a_i и строки x_j в таблице переходов ставится состояние a_s = d [ a_i,x_j ], в которое автомат перейдет из состояния a_i под воздействием сигнала x_j ; а в таблице выходов – соответствующий этому переходу выходной сигнал y_g = l [ a_i,x_j ].

Совмещенная таблица переходов и выходов автомата Мили:

Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но и также все три алфавита: входной, выходной и алфавит состояний.

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

Отмеченная таблица переходов автомата Мура :

В этой таблице каждому столбцу приписан, кроме состояния a_i , еще и выходной сигнал y ( t ) = l ( a ( t )), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Приведем примеры табличного задания автоматов Мили и Мура :

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

Для автомата Мили: Для автомата Мура :

2. Графический способ задания автомата (задание автомата с помощью графа)

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a_i и a_s соединяются дугой, направленной от a_i к a_s , если в автомате имеется переход из a_i в a_s , т.е. a_s = d ( a_i , x_j ). В автомате Мили дуга отмечается входным сигналом x_j , вызвавшим переход, и выходным сигналом y_g , который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

Источник

Конечный автомат: теория и реализация

Авторизуйтесь

Конечный автомат: теория и реализация

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

Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:

Примечание автора Хоть в статье используются ActionScript 3 и Flash, вы с легкостью можете писать на удобном для вас языке.

Что такое конечный автомат?

Конечный автомат (или попросту FSM — Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

Описание состояний автомата

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра — переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

Планирование состояний и их переходов

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

Описание состояний интеллекта муравья

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

3–5 декабря, Онлайн, Беcплатно

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

Обратите внимание на то, что при направлении домой или из дома муравей не будет бояться курсора мыши. Почему? А потому что нет соответствующего перехода.

Описание состояний интеллекта муравья. Обратите внимание на отсутствие перехода между «run away» и «go home»

Реализация простого конечного автомата

Конечный автомат можно реализовать при помощи одного класса. Назовем его FSM. Идея состоит в том, чтобы реализовать каждое состояние как метод или функцию. Также будем использовать свойство activeState для определения активного состояния.

Всякое состояние есть функция. Причем такая, что она будет вызываться при каждом обновлении кадра игры. Как уже говорилось, в activeState будет храниться указатель на функцию активного состояния.

Метод update() класса FSM должен вызываться каждый кадр игры. А он, в свою очередь, будет вызывать функцию того состояния, которое в данный момент является активным.

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM — это делает наш класс более универсальным.

Использование конечного автомата

Давайте реализуем ИИ муравья. Выше мы уже показывали набор его состояний и переходов между ними. Проиллюстрируем их еще раз, но в этот раз сосредоточимся на коде.

Описание состояний интеллекта муравья, сосредоточенное на коде

Наш муравей представлен классом Ant, в котором есть поле brain. Это как раз экземпляр класса FSM.

Класс Ant также содержит свойства velocity и position. Эти переменные будут использоваться для расчета движения с помощью метода Эйлера. Функция update() вызывается при каждом обновлении кадра игры.

Для понимания кода мы опустим реализацию метода moveBasedOnVelocity(). Если хотите узнать поподробнее на тему движения, прочитайте серию статей Understanding Steering Behaviors.

Ниже приводится реализация каждого из методов, начиная с findLeaf() — состояния, ответственного за поиск листьев.

Состояние goHome() — используется для того, чтобы муравей отправился домой.

И, наконец, состояние runAway() — используется при уворачивании от курсора мыши.

Улучшение FSM: автомат, основанный на стеке

Представьте себе, что муравью на пути домой также нужно убегать от курсора мыши. Вот так будут выглядеть состояния FSM:

Обновленное описание состояний интеллекта муравья

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

Решением такой проблемы является конечный автомат, основанный на стеке. В отличие от простого FSM, который мы реализовали выше, данный вид FSM использует стек для управления состояниями. В верхней части стека находится активное состояние, а переходы возникают при добавлении/удалении состояний из стека.

Конечный автомат, основанный на стеке

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

Переходы в FSM, основанном на стеке

Реализация FSM, основанного на стеке

Такой конечный автомат может быть реализован так же, как и простой. Отличием будет использование массива указателей на необходимые состояния. Свойство activeState нам уже не понадобится, т.к. вершина стека уже будет указывать на активное состояние.

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

Важно отметить, что при использовании конечного автомата на основе стека каждое состояние несет ответственность за свое удаление из стека при отсутствии необходимости в нем. Например, состояние attack() само должно удалять себя из стека в том случае, если враг был уже уничтожен.

Вывод

Конечные автоматы, безусловно, полезны для реализации логики искусственного интеллекта в играх. Они могут быть легко представлены в виде графа, что позволяет разработчику увидеть все возможные варианты.

Реализация конечного автомата с функциями-состояниями является простым, но в то же время мощным методом. Даже более сложные переплетения состояний могут быть реализованы при помощи FSM.

Источник