Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Тесты'
Анализ результатов ЕГЭ показал, что тема « Химическая организация клетки» для выпускников является проблемной. Для решения этой проблемы необходимо вы...полностью>>
'Тематика курсовых работ'
Типы правопонимания: право и насилие. Концепция логоцентризма и понятие права. Формалистическая и социологическая трактовка нормы в позитивизме....полностью>>
'Решение'
Решение Комиссии таможенного союза от 18.06.2010г. № 319 «О техническом Регулировании в таможенном союзе» (приложение № 2 «Положение о порядке формиро...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Конечные автоматы

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

Еще примеры применения конечных автоматов:

  • Виджет посредством конечного автомата — статья на данном сайте.

  • Статья о конечном автомате применительно к созданию виджета на сайте IBM.

Содержание

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

  • Пример автомата Мура

  • Программная реализация автомата Мура

    • Переходы состояний

    • Выходы состояний

    • Движок

  • Программная реализация автомата Мили

  • Представление автоматами систем без памяти

  • Резюме

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

Конечный автомат имеет конечное множество состояний. Под воздействием входных команд из некоторого конечного множества он может перейти в другое состояние и "выработать" некие значения выходных параметров.

Существуют несколько разновидностей конечного автомата. Здесь мы рассмотрим две из них — автомат Мура и автомат Мили.

В автомате Мура значения выходных параметров однозначно определяются состоянием, в котором он находится. При этом состояние, в которое он перейдет, однозначно определяется текущим состоянием и входной командой. Точнее, конечный автомат Мура характеризуется следующими пятью элементами:

  • С — конечное множество допустимых состояний;

  • X — конечное множество допустимых входных сигналов (команд);

  • Y — конечное множество допустимых выходных параметров (выходов);ˆ

  • trans(c,x) — функция переходов состояний, однозначно сопоставляющая любым допустимым состоянию и команде некоторое допустимое состояние;

  • out(c) — функция выходов, однозначно сопоставляющая любому допустимому состоянию некотрый допустимый выход.

Нередко к указанным пяти объектам добавляют еще начальное состояние автомата. Математически функции переходов и выходов записываются так:
,
где через x обозначена операция декартова произведения множеств С и X (это множество всевозможных пар состояние-команда).
Функция trans преобразует всевозможные пары (с,x) состояний-команд в состояния (элементы множества C); функция out преобразует любое состояние (элемент множества C) в некоторый выход (элемент множества Y).

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

Автомат Мили отличается от автомата Мура только функцией выхода, которая определена на множестве всех пар состояние-команда. Точнее, out(c,x) определяет выход автомата, который он будет иметь после подачи на него команды x, если при этом он находился в состоянии c. Любой конечный автомат Мили можно преобразовать в эквивалентный по поведению конечный автомат Мура, и наоборот.

Пример автомата Мура

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

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

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


Автомобиль, повернись:

Программная реализация автомата Мура

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

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

Переходы состояний

Для рассмотренного примера функцию переходов состояний можно представить с помощью следующего массива:

var trans=[ ]; // массив переходов состояний автомата

trans['анфас']=[ ];

trans['анфас']["направо"]="левая";

trans["анфас"]["налево"]="правая";

trans["анфас"]["кругом"]="зад";

trans['левая']=[ ];

trans["левая"]["направо"]="зад";

trans["левая"]["налево"]="анфас";

trans["левая"]["кругом"]="правая";

trans['правая']=[ ];

trans["правая"]["направо"]="анфас";

trans["правая"]["налево"]="зад";

trans["правая"]["кругом"]="левая";

trans['зад']=[ ];

trans["зад"]["направо"]="правая";

trans["зад"]["налево"]="левая";

trans["зад"]["кругом"]="анфас";

Здесь первый индекс массива trans есть имя состояния, второй индекс — имя команды, а значение — имя состояния, в которое должен перейти автомат из состояния, указанного первым индексом, по команде, которая указана вторым индексом.

Выходы состояний

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

var out=[ ]; // массив выходов автомата

out["анфас"] =function() {document.getElementById('myimg').src="front.jpg"}

out["левая"] =function() {document.getElementById('myimg').src="left.jpg"}

out["правая"]=function() {document.getElementById('myimg').src="right.jpg"}

out["зад"] =function() {document.getElementById('myimg').src="back.jpg"}

Движок

Движок конечного автомата определим как объект automat, которому при инициализации передаются в качестве параметров массивы trans (переходов) и out (выходов), а также начальное состояние stat. Свойство stat автомата сохраняет имя текущего состояния. Метод input(команда) обеспечивает выдачу команды на вход автомата. Метод output() вычисляет выход автомата. Вот возможный вариант конструктора объекта automat:

function automat(trans,out,stat){ // движок автомата

this.trans=trans; // массив переходов

this.out=out; // массив выходов

this.stat=stat; // текущее состояние

put=function(inp){ // ввод команд

if (inp){

this.stat=this.trans[this.stat][inp];

this.output=out[this.stat] // выход

}

return this.stat

}

this.output=out[this.stat];// выход

}



Похожие документы:

  1. «Базисные конечные автоматы» по специальности 01. 01. 09 – дискретная математика и математическая кибернетика (физико-математические науки) выполнена на кафедре «Высшая математика» Димитровградского инженерно-технологического института – филиала нияу мифи

    Документ
    ... каноническому конечному автомату. Описаны два алгоритма построения базисного конечного автомата, ... доказана корректность этих алгоритмов. Исследованы свойства базисного конечного автомата. Доказанные свойства базисного автомата ...
  2. Лекция 3 Исчисления. Формальные системы. Формальные грамматики. Автоматы

    Документ
    ... Sj, , 4.1. Автоматная (регулярная) грамматика – AГ и конечный автомат – КА. Автоматная грамматика , где А – основной ... алфавит; Р – правила вида – аксиома. Конечный автомат , где А – основной алфавит; S – алфавит состояний ...
  3. 1. Простейшие модели и система параметров логических элементов Даже самые сложные преобразования цифровой информации, в конечном счете, сводятся к простейшим оп

    Документ
    ... Реализация конечных автоматов В канонической схеме автомата ППЗУ может ... число выходов n = р + q следовательно, для реализации автомата требуется емкость памяти М = 2k+q(p + q). Воспроизведение ... состоя­ний автомата 2Г. Автомат рассматривается как ...
  4. Варианты домашних заданий по дисциплине «Теория автоматов»

    Документ
    ... автоматов. Параллельное соединение автоматов. Последовательное соединение автоматов. Автоматы с обратной связью. Минимизация конечного автомата. Эквивалентность автоматов. Автомат-«воспитатель». Автомат – банкомат. Автомат ...
  5. «Прикладная информатика» (2)

    Методическая разработка
    ... под термином «конечный автомат» всегда понимается детерминированный конечный автомат. Два автомата называем эквивалентными, ... проблемы синтеза по распознающему язык L конечному автомату К конечного автомата К* (вообще говоря, недетерминированного), ...

Другие похожие документы..