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


Оглавление (нажмите, чтобы открыть):

Определение конечного автомата

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

  1. C.4.1 Определение расширенных компонентов
  2. I. Определение.
  3. II. Определение численности АУП.
  4. А. Определение и интерпретация понятий
  5. Абсолютные показатели финансовой устойчивости. Определение типа финансовой устойчивости
  6. Абстрактное определение конечного автомата
  7. Аксиология – наука о ценностях. Истинностные и оценочные высказывания. Определение ценности. Структура оценки.
  8. Аксиоматическое определение вероятности.
  9. Алгоритм формирования системы логистического сервиса. Определение оптимального значения уровня логистического обслуживания
  10. Анализ риска. Определение и измерение риска. Кривая Фармера. Законодательные акты регламентирующие риск.
  11. Аналитическое определение передаточного отношения
  12. Анатомия конечного мозга

Теория конечных автоматов

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

· конечный автомат может решать ряд легких задач компиляции. Лексический блок почти всегда строится на основе конечного автомата.

· работа конечного автомата отличается высоким быстродействием.

· моделирование конечного автомата требует фиксированного объема памяти, что упрощает управление памятью.

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

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

Определение: Конечный автомат — это формальная система, которая задается с помощью следующих объектов [10]:

· конечным множеством входных символов;

· конечным множеством состояний;

· функцией переходов, которая каждой паре ( текущее состояние, входной символ) ставит в соответствие новое состояние;

· подмножеством состояний , выделенных в качестве допускающих или заключительных.

Пример. Разберем работу контроллера, проверяющего четно или нечетно число единиц в произвольной цепочке, состоящей из нулей и единиц. Допустим, что соответствующий конечный автомат должен « допускать» все цепочки, содержащие нечетное число единиц и « отвергать » цепочки с четным их числом. Назовем этот автомат « контроллером четности ». Считаем, что символы, отличные от 0 и 1 нельзя подавать на вход автомата. Итак, входной алфавит контроллера есть множество <0, 1>. Считаем, что в конкретный момент времени конечный автомат имеет дело лишь с одним входным символом, а информацию о предыдущих символах входной цепочки сохраняет с помощью конечного множества состояний. В качестве множества состояний будем рассматривать множество < чет, нечет >, одно из этих состояний должно быть выбрано в качестве начального. Пусть им будет состояние <чет>, поскольку на первом шаге число прочитанных единиц равно нулю, а нуль есть четное число. При чтении очередного входного символа состояние автомата либо меняется, либо сохраняется прежним причем новое его состояние зависит от входного символа и текущего состояния. Такое изменение состояния называется переходом.

Работа автомата может описываться математически функцией переходов вида d( Sтек., x ) = Sнов. Иначе это можно записать следующим образом:

d ( чет., 0) = чет. d ( чет., 1) = нечет.

d ( нечет., 0) = нечет. d ( нечет., 1) = чет.

Контроллер имеет единственное допускающее состояние НЕЧЕТ, а ЧЕТ есть « отвергающее » состояние. Отразим последовательность переходов автомата при подаче на его вход цепочки 1101.

ЧЕТ ® НЕЧЕТ ® ЧЕТ® ЧЕТ® НЕЧЕТ

Таблица переходов такого автомата имеет вид:

чет чет нечет
нечет нечет чет

Определение. Конечный автомат — это формальная система

объекты которой следующие:

* A — конечное множество входных символов (множество

* Q — конечное множество внутренних состояний автомата

* V — конечное множество выходных символов (выходной алфавит);

* d — функция переходов, для которой характерно A ´ Q ® Q;

* l — функция выходов, определяющая отображение вида :

| следующая лекция ==>
| Архитектура ЭВМ. Способы представления конечных автоматов

Дата добавления: 2014-01-20 ; Просмотров: 1890 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Глава 3. Конечные автоматы

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

В результате изучения материала этой главы читатель должен усвоить:

общее представление о конечноавтоматных преобразователях информации и их свойствах, методах их задания, особенностях двух основных типов конечноавтоматных преобразователей: автоматах Мили и Мура;

проблемы минимизации и проверки эквивалентности конечных автоматов;

методы реализации конечноавтоматных преобразователей;

примеры применения КА в различных областях и методы графического формализма конечноавтоматного представления систем обработки информации;

автоматные модели параллельных процессов

Содержание главы 3:

Автоматное преобразование информации

Эквивалентность КА: теорема Мура

Автоматы Мили и Мура

Схема управления микрокалькулятором

Протокол выбора лидера в распределенной системе

Визуальный формализм представления моделей систем с памятью: Statecharts

Автомат, регулирующий пешеходный переход

Графы переходов при спецификации и анализе параллельных программ

Проблема умножения: алгоритм, который не может выполнить КА

3.1 Автоматное преобразование информации

Не все окружающие нас преобразователи информации выполняют функциональное отображение информации. Результат преобразования входвыход зачастую зависит не только от того, какая информация в данный момент появилась на входе, но и от того, что происходило раньше, от предыстории преобразования. Огромное множество примеров тому дают биологические системы: например, один и тот же вход — извинение после того, как вам наступили на ногу в переполненном трамвае — вызовет у вас одну реакцию в первый раз и совсем другую в пятый раз, если вам постоянно наступают на ногу и извиняются. Таким образом, существуют более сложные, не функциональные преобразователи информации, реакция их зависит не только от входа в данный момент, но и от входной истории. Такие преобразователи называются автоматами. Даже если различных элементов входной информации у автомата конечное число (как в конечном функциональном преобразователе), количество возможных входных историй бесконечно (счетно). Если автомат по разному будет себя вести в дальнейшем для всех или бесконечного числа возможных предысторий, то такой “бесконечный” автомат должен иметь бесконечный ресурс — память, чтобы все эти предыстории запоминать. Объединим все “эквивалентные” предыстории в классы эквивалентности: две истории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Таким образом, автомат, реализующий не функциональное отображение, должен обладать памятью для запоминания входных историй или, как минимум, классов эквивалентности, к которым принадлежат истории. Случай, когда число классов эквивалентных входных историй конечно, является простейшим, однако, он вызвал значительный интерес и имеет очень широкие применения. Такая модель называется конечным автоматным преобразователем информации, или просто конечным автоматом.

Определение 3.1. (Внутренним) состоянием дискретного преобразователя назовем класс эквивалентности его входных историй.

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

Рис. 3.1. Автоматный преобразователь и его реализация

Пример 3.1.Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Граф автомата, моделирующего умное поведение родителя, представлен на рис. 3.2.

Рис. 3.2. Автомат, описывающий поведение отца

Здесь конечный автомат изображен графом с вершинами, соответствующими состояниям. Ребра графа соответствуют переходам между состояниями. Ребро помечено входным сигналом, под воздействием которого этот переход происходит, и выходным сигналом, который вырабатывает автомат при получении этого входного сигнала в текущем состоянии. Автомат, моделирующий родителя, имеет четыре состояния , и два входных сигнала — оценки, полученные сыном в школе: <2, 5>. Начиная с начального состояния s0 (оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы — реакции на входы. Выходы автомата будем интерпретировать как действия родителя так:

у0: — брать ремень;

у1: — ругать сына;

у2: — успокаивать сына;

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

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

Определение 3.2. Конечным автоматом Мили называется шестерка объектов: А= , где:

S — конечное непустое множество (состояний);

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

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

sS — начальное состояние;


: SXS — функция переходов;

: SXY — функция выходов.

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

Реализация конечных автоматов на функциональных языках программирования Текст научной статьи по специальности « Автоматика. Вычислительная техника»

Аннотация научной статьи по автоматике и вычислительной технике, автор научной работы — Малаховски Я. М., Шалыто А. А.

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

Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Малаховски Я. М., Шалыто А. А.,

Automata implementation in functional programming languages

This article discusses the problems of implementation of the Shalyto’s finite state automata in functional programming languages. The advantages of proposed implementations over imperative implementations in traditional programming languages (C, Pascal) are shown.

Текст научной работы на тему «Реализация конечных автоматов на функциональных языках программирования»

программные и аппаратные средства X

реализация конечных автоматов на функциональных языках программирования

магистрант А. А. Шалыто,

доктор техн. наук, профессор

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

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

Ключевые слова — конечные автоматы, функциональное программирование, Haskell.

Несмотря на все более широкое использование автоматных моделей при разработке программного обеспечения, в настоящее время не известно методов реализации на функциональных языках программирования [1] событийных структурных конечных автоматов, используемых в автоматном программировании [2].

Основное отличие функциональных программ от императивных состоит в том, что функциональная программа представляет собой некоторое выражение (в математическом смысле), а выполнение программы означает вычисление значения этого выражения. При этом слово «вычисление» вовсе не означает, что операции производятся только над числами.

При сравнении «чистого» (pure) функционального и императивного подходов к программированию можно отметить следующие свойства функциональных программ:

• в чистых функциональных программах отсутствуют побочные эффекты, поэтому в них не существует прямого аналога глобальным переменным и объектам императивных языков программирования;

• в функциональных программах не используется оператор присваивания;

• в функциональных программах нет циклов, а вместо них применяются рекурсивные функции;

• выполнение последовательности команд в функциональной программе бессмысленно, по-

скольку одна команда не может повлиять на выполнение следующей.

Отсюда следует, что при использовании чистых функциональных языков программирования (например, языка Haskell) не удается непосредственно применять методы, используемые при реализации конечных автоматов на императивных языках программирования (например, языка C++). Это объясняется тем, что состояние автомата, по сути, является глобальной переменной, а обработка последовательностей событий в императивных языках производится при помощи циклов.

В теории конечных автоматов существуют два класса: абстрактные и структурные автоматы. Абстрактные автоматы обычно используются при разработке систем генерации парсеров по контекстно-свободным грамматикам и регулярным выражениям (см., например, работы [3, 4]). Функции переходов в таких задачах обычно строятся не по диаграммам состояний, а по множеству порождающих правил. В свою очередь, реализации на императивных языках программирования, построенные по диаграммам состояний, обычно валидируются сторонними утилитами, а не компилятором.

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

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

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

В работе используется язык Haskell [5-8], так как:

• в отличие от иных подобных языков, он близок к типизированному лямбда-исчислению;

• в нем отсутствуют побочные эффекты;

• он не нарушает функциональные концепции при вводе-выводе.

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

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

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

Обработка одиночных событий.

Пусть требуется реализовать счетный триггер (рис. 1), реагирующий на события. Другими словами, требуется построить конечный автомат с двумя состояниями, кодируемыми нулем и единицей, который управляется кнопкой. Каждое нажатие кнопки порождает событие е. К выходу 2 конечного автомата подключена лампа. Каждое событие е переводит автомат в состояние (1 — у), где у — текущее состояние. При этом переменная состояния одновременно является выходной переменной (2 = у). Таким образом, каждое нажатие кнопки будет приводить то к включению лампы,

■ Рис. 1. Диаграмма состояний счетного триггера

то к ее выключению. Исходный код, реализующий данный счетный триггер, приведен в листинге 1.

Листинг 1. Реализация счетного триггера на Haskell.

— Событие: «Нажатие на кнопку». data Event = ButtonClick deriving Show — Состояния: «Выключено» и «Включено». data State = LampOff | LampOn deriving Show

— Функция переходов, изоморфная рис. 1. gotEvent :: State -> Event -> State gotEvent LampOff ButtonClick = LampOn gotEvent LampOn ButtonClick = LampOff

— Функция, вызываемая системой.

— Начальное состояние — LampOff. main = print $ gotEvent LampOff ButtonClick

Рассмотренная реализация функции переходов не является единственно возможной. Например, для этой цели можно использовать конструкции pattern matching. Однако в этом случае исходный код обычно получается длиннее, поскольку такая конструкция требует частичного дублирования. Поэтому в дальнейшем будет использоваться оператор case.

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

Листинг 2. Функция applyEvents и ее использование.

— Исходный код листинга 1 за исключением функции main

— Функция, применяющая события к начальному состоянию. applyEvents :: State -> [Event] -> State — Результат = состояние, если событий больше нет. applyEvents st [] = st

— Иначе делаем переход и вызываемся рекурсивно. applyEvents st (e:es) = applyEvents (gotEvent st e) es

— Новая функция main.

main = print $ applyEvents LampOff [ButtonClick]

Обобщение на произвольные типы данных для событий и состояний.

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

Листинг 3. Библиотечная функция apply-Events и ее использование.

— Тип функции переходов.

type SwitchFunc state event = state -> event -> state

— Функция, применяющая список событий к начальному — состоянию автомата при помощи функции переходов. applyEvents :: SwitchFunc st ev -> st -> [ev] -> st applyEvents _ st [] = st

applyEvents swF st (ev:evs) = applyEvents swF

— Реализация счетного триггера

— при помощи приведенного выше библиотечного кода.

— Типы событий и состояний для счетного триггера. data TriggerEvent = ButtonClick deriving Show data TriggerState = LampOff | LampOn deriving Show — Функция переходов для счетного триггера. triggerSwF LampOff ButtonClick = LampOn triggerSwF LampOn ButtonClick = LampOff

— Функция, вызываемая системой.

main = print $ applyEvents triggerSwF LampOff [ButtonClick]

Отметим, что новая версия функции apply-Events (листинг 3) является левой сверткой (одна из стандартных операций функционального программирования) списка событий по функции переходов. Поэтому можно заменить все определение функции applyEvents на applyEvents = foldl.

Преимущества функциональной реализации.

Алгебраические типы данных позволяют производить более строгие проверки по сравнению с конструкциями, сходными с конструкцией enum императивного языка С. Например, при использовании алгебраических типов данных невозможно случайно проверить на равенство элемент множества состояний с элементом множества событий. Еще одним преимуществом функционального подхода является то, что компилятор способен самостоятельно проверить полноту и непротиворечивость веток оператора case, тем самым осуществляя валидацию функции переходов на этапе компиляции.


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

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

■ Рис. 2. Диаграмма переходов счетного триггера с четырьмя состояниями

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

Листинг 4. Общая часть реализаций счетного триггера с четырьмя состояниями.

— Типы событий и состояний для счетного триггера. data TriggerEvent = ButtonDown | ButtonUp deriving Show

data TriggerState = LampOffButtonUp LampOffButtonDown LampOnButtonUp LampOnButtonDown deriving Show

Первый вариант реализации выходных воздействий.

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

Листинг 5. Функция переходов, возвращающая список выходных воздействий.

— Абстрактный тип функции переходов,

— возвращающей новое состояние и список выходных воздействий.

type SwitchFunc state input output = state -> input -> (state, [output])

— Функция applyEvents, реализованная через свертку. applyEvents :: SwitchFunc state input output -> state -> [input] -> (state, [output]) applyEvents switchFunc state events = foldl (switchToAcc switchFunc) (state, []) events

— Функция, «конвертирующая» функцию переходов в

— аккумулятор выходных воздействий. switchToAcc :: SwitchFunc state input output -> (state, [output]) -> input -> (state, [output]) switchToAcc switchFunc (state, output) event =

(nstate, output ++ noutput)

where (nstate, noutput) = switchFunc state event

— Функция переходов для счетного триггера. triggerSwitchFunc state event = case state of LampOffButtonUp -> case event of ButtonDown -> (LampOffButtonDown, [])

LampOnButtonUp -> case event of ButtonDown -> (LampOnButtonDown, [])

LampOffButtonDown -> case event of ButtonUp -> (LampOnButtonUp, [putStrLn «LampOn»])

LampOnButtonDown -> case event of ButtonUp -> (LampOffButtonUp, [putStrLn «LampOff»])

— Функция, вызываемая системой. main = do sequence_o putStrLn $ show $ s where

(s, o) = applyEvents triggerSwitchFunc LampOffButtonUp [ButtonDown, ButtonUp, ButtonDown, ButtonUp]

Второй вариант реализации выходных воздействий.

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

Листинг 6. Функция переходов, возвращающая список выходных воздействий.

— Абстрактный тип функции переходов,

— возвращающей новое состояние и осуществляющей IO. type SwitchFunc state input output = state -> input -> IO state

— Функция applyEvents, реализованная через монаду IO. applyEvents :: SwitchFunc state input output -> state -> [input] -> IO state

applyEvents switchFunc state [] = return state applyEvents switchFunc state (event:eventsTail) = do newstate case event of ButtonDown -> return LampOffButtonDown _-> return state LampOnButtonUp -> case event of ButtonDown -> return LampOnButtonDown _-> return state LampOffButtonDown -> case event of

ButtonUp -> do putStrLn «LampOn» return LampOnButtonUp _-> return state LampOnButtonDown -> case event of ButtonUp -> do putStrLn «LampOff» return LampOffButtonUp _-> return state

— Функция, вызываемая системой. main = do

result i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

1. Abelson H., Sussman G. Structure and Interpretation of Computer Programs. — MIT Press, 1985. — 634 p.

2. Поликарпова Н. И., Шалыто А. А. Автоматное программирование. — СПб.: Питер, 2009. — 176 с.

3. Parsec. https://www.haskell.org/haskellwiki/Parsec (дата обращения: 09.07.2009)

4. The Parser Generator for Haskell. https://www. haskell.org/happy/ (дата обращения: 09.10.2009).

5. Bird R. Introduction to Functional Programming using Haskell. — NY.: Prentice Hall, 1998. — 448 p.

6. Davie A. Introduction to Functional Programming System Using Haskell. — Cambrige: Cambrige University Press, 1992. — 304 p.

Электроника для всех

Блог о электронике

AVR. Учебный курс. Конечный автомат

Каждый кто пытался разбираться с конечными автоматами наверняка натыкался на всякие замудреные графы, какие то графики. Многие посчитав это слишком сложным плюнули и забили. А Зря!

С простейшим конечным автоматом каждый из нас сталкивался с самого детства — это механическая авторучка. Объект с единственной функцией «Нажатие кнопки», но в зависимости от очередности результат разный. Стержень то прячется, то вылазит.

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

; Глобальные переменные u08 Blink_State; vo >

Вызывая эту функцию подряд мы заставим диодик менять свое состояние при каждом вызове.

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

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

Пусть у нас есть сигнал:

Цифрами указана задержка, в каких нибудь величинах. Это не суть важно.

Обычно народ не парится и лепит его по быдлокодерски, через delay:

Set_Pin(); // Вывод в 1 Delay(10); // Задержка 10 Clr_Pin(); // Вывод в 0 Delay(100); // Задержка в 100 Set_Pin(); Delay(1); Clr_Pin(); Delay(5); Set_Pin(); Delay(2); Clr_Pin(); Delay(3); Set_Pin; Delay(4); Clr_Pin();

Это дает минимальный код, но затыкает работу контроллера на весь период посылки. А если слать надо постоянно? Да еще дофига всего попутно делать? Экран обновлять, данные обрабатывать, в память писать…
В таком случае у нас рулит RTOS, где на Delay происходит передача управления диспетчеру. Но если ОС нету? Вот тут то и идет в ход конечный автомат.

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

А запускается эта байда простым пинком:

Set_Pin(); TCNT=255-10; // Грузим таймер на выдержку 10 тиков TMR_State = 0; // Устанавливаем начальное положение Timer_ON(); // Поехали! . // После чего можно заниматься чем угодно.

Когда автомат отработает — сама себя выключит. Можно еще какоенить событие сгенерировать, дабы основная программа поняла, что все уже готово. Хотя основная программа спокойно может палить переменную состояния автомата и все оттуда узнать сама.

Конечный автомат можно зациклить — скажем на стадии 6 сделать перенаправление на стадию 0, то получим генератор сигнала сложной формы. Причем он будет занимать минимум процессорного времени.

Если мы, например, захотим сделать десяток ШИМ сигналов? То что нам мешает повесить их на ОДИН таймер, главное отсортировать все скважности по возростанию, причем сортировать их вместе с ногами которыми нужно дрыгать. А потом прогнать по прерыванию таймера конечный автомат, да так чтобы он по стадиям передергивал ножки. Правда при изменении скважности любого из этих софтверных ШИМ каналов придется делать повторную сортировку всего массива. Разумеется больших скоростей мы на этом не получим. Таймер не может щелкать так быстро, да и математики там хватит. Но для многих задач, например, одновременное управление десятком сервомашинок этого более чем достаточно.

Мастер Йода рекомендует:  JWT простым языком что такое JSON токены и зачем они нужны

А если в том же прерывании таймера сделать выбор следующей стадии исходя не из тупой последовательности, а, скажем, на основе обрабатываемого байта, то мы получим программно-аппаратный генератор, к примеру, 1-Wire кода. Достаточно анализировать входной буфер и если там 1 — перебрасывать автомат в состояние соответствующее отработки генерации сигнала 1, а если 0, то в состояние генерящее выдержку нуля.

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

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

Особенно автоматный метод доставляет тем, что готовые автоматы вписываются как родные в ЛЮБУЮ почти архитектуру. У меня они и во флаговых автоматах работают на ура, и из диспетчера RTOS я их гоняю как родные. Красота!

70 thoughts on “AVR. Учебный курс. Конечный автомат”

Вообще, конечные автоматы — базовое знание для любого программиста.
Нужно понимать, что и компьютер, и микроконтроллер как частный случай, и любая программа — конечный автомат, пусть и довольно сложный.
Понимание этого факта дает возможность по-новому взглянуть на код, и нередко нефигово его упростить.
Плюс можно сделать суперкомпактную выжимку алгоритма, отделив его от кода обработки самого автомата — загнать состояния и условия перехода между ними в массив какой-нибудь.
Одним словом, КА — рулят!

Ага, только к МК обычно идут от железа, от электроники, а там программированию не учат. В результате получаются такие программные монстры, что страшно становится. С ужасом вспоминаю свои программы пятилетней давности.

Так если б программистов нормально учили, а то ведь та же фигня, КА нам прочли только на третьем курсе. Чего теперь стоит отучиваться писать говнокод…


Нас на специальности 2205 «проектирование и производство электронно-вычислительных средств» тоже програмированию как таковому почти не учили (все свелось к изучению Паскаля), но вот микропрограммные автоматы шли сразу же в курсе цифровой схемотехники.

Чего-чего? А, гугль подсказывает, есть такие кафедры…
Не. Кафедра ЭВС (ранее — КЭВА), МарГТУ (ранее — МарПИ).

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

Меня во время учёбы очень зацепили микропрограммные автоматы — простая ПЗУ плюс регистр-защелка плюс тактовый сигнал — и можно наворотить нечто, что казалось бы, требует целого процессора. Хотя процессор так и устроен, ага — только добавляются АЛУ, РОН и прочие блоки.

Я с ПЗУ делал лет 10 назад много чего интересного 🙂 Управление ксетником, робота маленького…. Даже делал 4ьитный калькулятор..

А как АЛУ реализовывалось? Таблично?

Да 🙂 было использовано на всё это 6 штук РЕ5

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

Довелось мне делать технический диплом на заказ, так вот там впервые столкнулся с КА. С его помощью там была организована работа клавиатуры. Довольно сложная в реализации, с первого взгляда. А с помощью конечного автомата — не более страницы вот таких case’ов. Тогда я только понял как это работает в программе, а теперь, прочитав статью — «достиг просветления» =)
Осталось что-то своё написать пару раз — и умение свернётся в навык.

И у нас был курс по этим автоматам! Я его прошел и забыл, но суть уяснил. Успешно использую это знание в своих работах =)

Уважаемый DI HALT, всегда с интересом и вдумчивостью читаю Ваши статьи, как «железные», так и «софтовые». Не могли бы Вы написать статью по поводу фильтров, рассчёт, применение, ну и всё сопутствующее. Уверен подобная статью будет интересна к прочтению для всех посетителей сайта.

Эт не моя тема, не думаю что я там дам толковый совет.

Значит будем ждать новые статьи по Вашей теме, спасибо.

А что конкретно вас интересует в расчете? Использование Матлаба или другой способ подгонки коэффициентов? Или что то другое?

Так вот как это называется, каонечные автоматы))) Я так серваками управлял, правда не знал как этот алгоритм наз-ся) Спасибо, посоветуйте, пож-та книжку какую-нибудь понятно написанную по теории конечных автоматов.

Спасибо за интересную статью. А что если сделать по другому? Например, по каждому прерыванию таймера (CTC), вызывать функцию, которая циклически пролистывает задачи.
Псевдокод:

Чем плох такой подход?

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

Прямую передачу можно присобачить, тем более, что пример есть в статье 🙂
Кстати, а зачем временная задержка нужна?

Какая временная задержка?

case 0:
<
Clr_Pin(); // Вывод в 0
TCNT = 255-100; // Задержка в 100 (до переполнения)
TMR_State = 1; // Следующая стадия 1
Break; // Выход
>

Вот эта -> // Задержка в 100 (до переполнения)

Ну так это — параметры генерируемого сигнала посмотри. =)

Точно, протирание глаз иногда помогает 🙂 Т.е. основная цель — это генерация такого сигнала. А так по сути, если такие интервалы не критичны, то задержка нафиг не нужна.

imho, переменную состояния лучше запихнуть внутрь функции и объявить как статическую, ибо чем меньше область видимости, тем меньше потом придется разбираться с непонятными зависимостями и побочными эффектами:

А если захочется изменить ее извне? В более сложных премерах это сплошь и рядом.

ИМХО, когда захочется её изменять из вне, тогда и надо её выносить в глобальную область видимости, а пока такой необходимости нет, то лучше пусть она будет локальной.

Присоединяюсь. Инкапсуляцию не зря придумали.

Вот как понадобится — так и вытаскивать.
Чем меньше в системе связей, тем проще ее развивать или чинить-диагностировать.

Еще удобная фишка — область видимости в пределах файла.
Этакий «почти класс», но чистое Си без использования приплюснутых расширений.

Кстати, по поводу стилей оформления исходников.
Я предпочитаю так:
фигурные скобки всегда с новой строки.
Весь блок внутри скобок сдвинут вправо относительно скобок на два пробела.
Не помню, откуда этот стандарт, но так реально удобнее читать, особенно если вложенность хотя бы пять-шесть.

То есть, в «моём» примере кода 3,4,10 строки надо сдвинуть вправо на 2 пробела, 5,9,11,15 писать с отступом в те же два пробела, 6-8 и 12-14 писать с отступом в 4 пробела.

Ну и, на правах паранойи, вместо «if ( var == 1 )» лучше писать «if ( 1 == var )», особенно если настройки компилятора не дают предупреждение на опечатку вида «if ( var = 1 )».

Ага, всё это вполе субъективно-религиозно, а не Великая Истина.

Круто! Не догадался бы. Возьму на вооружение.

Мне тоже понравилось 🙂 Мерси, nicka

маньяки, блин! больше кнопок нажмете, больше калорий потратите ))
чем ваc if(var) или if(!var) не устраивает?
давайте тогда уж x=x+1 писать ))

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

Ну, например, так:

Строка таблицы содержит
1) номер текущего состояния
2) код условия перехода («терминальный символ»)
3) ссылка на действие, выполняемое при переходе
4) номер нового состояния

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

Пример есть в статье Александра Черномырдина https://is.ifmo.ru/progeny/_autmicroc.pdf

Только вот если входные условия разнородны, потребуется формирователь терминальных символов. (У Владимира Кожаева это названо «контейнер условий перехода» — см. https://www.slideshare.net/uafpug/ss-4604587 )

вот этот «формирователь терминальных символов» всю малину и портит. Условия достаточно сложны (присутствуют вычисления и обработка массивов), чтобы получилась окидываемая взглядом программ автомата. И получается, что по сути терминальных символов всего три-четыре (авария, стоп, переход к следующей фазе, возврат к фазе N), но вычисление их — функция на пять листов, с зависимостью от текущего состояния. Действия тоже достаточно сложные (задать параметры ПИД-регуляторов, например). И красивой структуры не выходит. Красивой именно в том плане, что глазом посмотрел и все понятно.

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

А так забыл поставить break в каком-то развесистом case — и вылезет это боком через год на реальном оборудовании.

По-моему получилось не менее былокодерски. Не лучше ли сделать массив с длительностью задержек и при каждом прерывании простым кодом брать из него значение? По идее такой способ и места в прошивке будет меньше занимать. А при генерации сигналов длиной 30 и более шагов разница будет очень очевидна 🙂

А кто тебе сказал что это конечное решение? И суть тут не в массиве, а в подходе.

Коллега!
Мигалка на псевдокоде мигать не будет! Будет всегда выключена, потому что второй иф выполнится сразу же за первым

Внимательнее смотри код, там return.

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

Статья как нельзя кстати. На дня нашел вот такое вот чудо:

C/C++ Open Source State machine framework. Может интегрироваться в некоторые, популярные RTOS. Поддержка AVR (под WinAVR / IAR).

Очень хотелось бы заюзать, да только для начала неплохо бы вникнуть в саму суть конечных автоматов.

Любопытно! Но я не совсем понял..
Суть — использование таймера. Таймер аппаратный, работает быстро, и не вешает программу на время задержек.
Это замечательно и верно. Используем таймеры вместо задержек.
Зачем введено понятие «конечный автомат»? Определения позволяют лаконично изъясняться, но в данном случае рекомендация «используй конечный автомат» разве несёт информации больше чем «используй таймер»?

Таймер может сделать только ОДНУ какую либо выдержку. Как сделать так, чтобы ОДИН таймер поочередно реализовал массу выдержек, причем сделал это сам, без вмешательства фоновой программы? С помощью конечного автомата.

Полезная штука. А как такое на асме реализовать? Каким способом?

Вариантов масса. Начиная с бального комплекта
LDS R16,Avtom_state
CPI R16,value
BREQ nnn
CPI R16,value
BREQ mmm
CPI Rn,value
BREQ kkk

До создания таблицы переходов, где Avtom_state будет создавать смещение в таблице, где лежит адрес перехода.

О, большое спасибо. Но если у меня около 30 операций в автомате, разница-то во времени выбора каждого действия будет разная. Правильно я понимаю?

Если на CPI банде то да. Чем глубже тем дольше. А если на таблицах перехода то нет. Каждый кейс будет обрабатываться за одинаковое количество тактов.

error: Relative branch out of reach

Не подскажете, что это за ошибка? Точнее из-за чего она? У меня сразу в обработчике стоят сравнения.

CPI R19,1
JMP stolb_1

CPI R19,2
BREQ stolb_2

CPI R19,3
BREQ stolb_3

Бранч который в BREQ не умеет прыгать дальше чем 127 (или даже 64) команды вверх или вниз. У тебя просто он не достает до метки.

Обычно в таких случаях делается островок вида:
RJMP Obhod
m: RJMP M
m2: RJMP M2
Obhod:
…..

и делается проброс бранча через джамп дальше,куда тебе надо. Но это херня, код превращается в кашу. Лучше юзай табличный переход.
https://easyelectronics.ru/avr-uchebnyj-kurs-vetvleniya.html


Примеры сделаны на пинбоорде v1.1, для тех кто не сильно понимает язык С++ (хотя я осознаю что рано или поздно надо будет и им овладеть, но пока мне и asm хватает, аппетит приходит как говориться во время еды _)
Конечный автомат (state machine, машина состояний) представляет собой устройство, имеющее внутреннюю память (переменные состояния), а также набор входов и выходов.
Работа автомата состоит в том, что он анализирует состояния своих входов, и, в зависимости от значений входов и своего внутреннего состояния, изменяет значения выходов и внутреннее состояние. Правила, в соответствии с которыми происходит изменение:
1. диаграммой переходов или
2. описываются таблицей.
Диаграммы как я понял по ходу дела составляются из блок схем, нарисовать не могу, т.к. не знаю как вставит в коменты (отзывы) картинку, но код мне кажется должен выглядеть вот так:

iini: cbi ddrD,6; инициализация, настройка кнопки на подтяжку sbi portD,6; PullUP knopka: sbic pinD,6; тест кнопки на rjmp knopka; 0 – GND ;—————————————— ;Задержка опроса кнопки тупым циклом т.к. таймерами я еще не овладел, в процессе еще … извините. LDI R26,255;LowByte; LDI R27,255;MidleByte; LDI R28,4;HighByte; loop1: SUBI R26,1; SBCI R27,0; SBCI R28,0; BRCC Loop1; ;——————————————— status: sbrc r16,0; Пропустить если бит в регистре очшищен rjmp led_on; перескок к метке led_on rjmp led_of; перескок к метке led_of led_on: sbi ddrD,7; на выход нога sbi portD,7; поднять ногу ldi r16,0b00000000; сохранить состояние автомата в регистр rjmp knopka; переход на ожидание нажатия кнопки led_of: cbi ddrD,7; нога на вход cbi portD,7; вырубить ногу ldi r16,0b00000001; сохранить состояние автомата rjmp knopka; переход на ожидание нажатия кнопки

В качестве ячейки сохранения состояния автомата в данном случае был использован регистр r16, (что бы таким как я было понятнее суть) и в нем (r16) можно было бы сохранить 256 различных состояний автомата, НО как я понял можно использовать вместо одного регистра любую ячейку не только РОН, но и RAM, ROM, EEROM и т.д. (включая внешние накопители), где можно было бы сохранить и считать биты статуса. (вопрос лишь в скорости и целесообразности ясный пень что РОН и RAM самый быстрые ячейки).
2. описываются таблицей.

;Резервирование ячейки в ОЗУ: .DSEG ; сегмент RAM (ОЗУ) для Мега16 начинается с $0060, (см. *.inc на тип контроллера) status: .BYTE 1; зарезервировали 1 байт в ОЗУ .CSEG ; кодовый сегмент ; Настройка кнопки D6 и очистка ячейка status в ОЗУ. ini: cbi ddrD,6; надо обнулить направление, sbi portD,6; поднять PullUP clr r16; очистка регистра sts status,r16; для того что бы обнулить ячейку в ОЗУ ; Проверка на нажатие кнопки с помошью флага Т knopkaa: in r17,pinD; чтение из порта save в регистр ;—————————————— ;Задержка опроса кнопки тупым циклом т.к. таймерами я еще не овладел, в процессе еще … извините. LDI R26,255;LowByte; LDI R27,255;M >

Мне так кажется что табличный вариант лучше, удобнее (читабелнее и в отладке в самый раз), выглядит стройнее, не говоря о комбинации с косвенным переходом, (без перебора значений), не говоря о практически безграничной (размер таблицы переменных значений состояний автомата в ОЗУ, уже в голове созрел коварный план заныкать таблицу в ОЗУ в конце, а SP поднять выше таблицы.)
p/s: примеры у меня работают не забывайте выставить конец стека и во втором примере зарезервировать байт в ОЗУ.

ну вот опять выглядит не очень, табуляцию не поддерживает да? Видимо надо было пробелами двигать. Пожаулуйста Di Halt подправь мой комент так что бы было видно для тех кто только учится.

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

Таблицы переходов они же статичные и нет никакого смысла ныкать их в ОЗУ. Только зря оперативку забивать. Клади их в флеш и доставай через LPM как я в примере переходов делал. И будет тебе счастье. А переменная состояния автомата она же индекс таблицы. На одном байте даст тебе 256 вариантов. Единственное надо терминировать или запрещать несуществующие варианты, иначе будет очень и очень плохо.
Это можно сделать маскированием, а лучше сделать таблицу на полные 256 байт (не так уж это и много), но забить ее переходом, скажем, на ресет. Или, лучше, в цикл ловушку — бесконечный цикл, с прицелом на то, чтобы вачдог перезагрузил контроллер. Чтобы если автомат сбойнул, то автоматом сразу же сбросило контроллер.

уже в голове созрел коварный план заныкать таблицу «STATUS» (таблицу-ячейки состояний) в ОЗУ в конце, а SP поднять выше таблицы»
ошибочка в торопях вышла не дописал слово. А так понятно что таблица состояний в ОЗУ, а таблица косвенных переходов в Флеше. (спасибо что поправили -)).

да и там (в ОЗУ) мы можем задать столько состояний автомата сколько захотим, т.к. уже два бита нам дадут 65 535 состояний автомата, а ячеек там за вычетом начальных адресов для Мега 16, 0x45F-0x60=0x3ff(если я правильно понимаю то это 256 в 1024 степени, короче говоря очень много), а РОН можно и не трогать, в любом случае ячеек в ОЗУ больше чем 32 ячейки РОН.

Вообще обычно РОН рассматривают как ячейки временного хранения действительные только в данном обработчике или в данном прерывании. Целенаправленно какие то данные в течении всей программы в них никогда не хранят. Или делают так очень редко да в небольших программках. Иначе и ошибок больше и налажать больше шансов.

Все данные нычут в озу. Благо в одну команду можно достать-сохранить данные без особых проблем.

В коде так и есть значения автомата (status) в ОЗУ
______________________________________________________
.DSEG ;
status: .BYTE 1; зарезервировали 1 байт в ОЗУ
______________________________________________________
А значения таблица переходов во Флеше:
______________________________________________________
.CSEG ; кодовый сегмент
…..
rjmp mimo;
tablica1: .dw led_on_D7, led_of_D7;
mimo: nop;
______________________________________________________

Конечные состояния машины — Finite-state machine

Конечный автомат ( КА ) или конечно-автомат ( FSA , множественное число: автоматы ), конечный автомат , или просто состояние машины , представляет собой математическую модель вычислений . Это абстрактная машина , которая может быть в точности один из конечного числа состояний в любой момент времени. FSM может меняться от одного состояния в другое в ответ на некоторые внешние входы ; переход от одного состояния в другое, называется переход . ФСМ определяется списком своих состояний, исходного состояния, а также условия для каждого перехода. Конечные автоматы двух типов — детерминированные конечные автоматы и недетерминированные конечные автоматы . Детерминированный конечный автомат может быть построен эквивалентен любым недетерминированными один.

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

Конечный автомат имеет меньшую вычислительную мощность , чем некоторые другие модели вычислений , такие как машина Тьюринга . Вычислительное различие мощности означает , что есть вычислительные задачи , что машина Тьюринга может сделать , но FSM не может. Это объясняется тем , что FSM в память ограничена числом состояний он имеет. Конечные автоматы изучаются в более общей области теории автоматов .

содержание

Пример: монетный турникет

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

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

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

Текущее состояние вход Далее государство Выход
запертый монета разблокирована Разблокирует турникет, так что клиент может протолкнуть.
От себя запертый Никто
разблокирована монета разблокирована Никто
От себя запертый Когда клиент протолкнул, блокирует турникет.

Турникета конечный автомат также может быть представлена в виде ориентированного графа называется диаграмма состояний (выше) . Каждое состояние представлено узлом ( окружность ). Ребра ( стрелка ) показывают переходы из одного состояния в другое. Каждая стрелка маркирована с входом , который вызывает этот переход. Вход , который не вызывает изменение состояния (например, монета вход в разблокирована состоянии) представлен круговой стрелкой возвращения в исходное состояние. Стрелка в Locked узел из черной точки указывает на то, что это начальное состояние.

Основные понятия и терминология

Состояние является описанием состояния системы , которая ждет , чтобы выполнить переход . Переход представляет собой набор действий , которые будут выполняться , когда условие выполняется , или когда событие принимается. Например, при использовании звуковой системы , чтобы слушать радио (система находится в состоянии «радио»), получив «Next» результаты стимула при переходе к следующей станции. Когда система находится в состоянии «CD», «следующий» результаты стимула при переходе к следующему треку. Одинаковые раздражители вызывают различные действия в зависимости от текущего состояния.

В некоторых конечно-машинных представлениях, можно также связать действия с государством:

  • действие записи: выполняется при входе в состоянии, и
  • действие выхода: выполняется при выходе из состояния.

Техническая документация

разработка техдокументации

Автоматное программирование для начинающих

В рунете лежит великолепная, но трудная для начинающих статья Б. П. Кузнецова «Психология автоматного программирования». Для специалистов не секрет, что знание принципов автоматного программирования дает возможность почти бездумно (и безошибочно), «пальцами» писать программы высочайшего уровня сложности. Редакция от 20.06.2020.

Автоматное программирование для начинающих

Создан 29.05.2005 9:49:02

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

Теорию автоматов преподают не везде. В технических ВУЗах преподают эту теорию применительно к синтезу цифровой аппаратуры, но не применительно к программированию (Такие выводы сделаны моим коллегой Шалыто А. А. для ведущих Питерских ВУЗов).

Автор прав. К сожалению, теория конечных автоматов и формальных языков читалась далеко и не в каждом московском ВУЗе. Автору настоящей статьи, выпускнику факультета электронной техники МЭИ, теория сия не читалась тоже. О существовании теории конечных автоматов было вскользь упомянуто в курсе цифровой схемотехники.

Жизнь — штука тонкая. Многим, кто окончил технические ВУЗы в начале (середине) восьмидесятых, пришлось не единожды менять область деятельности. Схемотехник вдруг начинал заниматься тонкопленочной технологией производства интегральных схем, специалист по электровакуумным приборам «вклинивался» в микропроцессорную схемотехнику. Выручало полученное в советских ВУЗах «широкое» образование, «ничего обо всем». Спасибо дорогому Леониду Ильичу за наше счастливое детство .

Автора настоящей статьи, как и «других похожих», жизнь (году в 1994-ом) вынудила забросить любимое «паяло» и погрузиться в разработку программ. По мере усложнения задач логики, здравого смысла, ВУЗовских знаний и навыков программирования, полученных самостоятельно, стало не хватать. Нехватка особенно сказывалась при разработке «коммуникационных» программ, реализации протоколов обмена данными. Организация взаимодействия пары модемов, обменивающихся данными по телефонной линии, казалась (в те времена) автору задачей почти неразрешимой.

Помощь подоспела вовремя со стороны старших товарищей, выпускников ВМиК МГУ, посвятивших автора настоящей статьи в основы теории конечных автоматов и показавших примеры реализации указанной теории на практике (одним из них — по странному стечению обстоятельств — был тоже Кузнецов, но другой). Достаточно сложный протокол обмена данными, работающий «поверх» протоколов физического и вышележащих уровней (транспортного, сетевого, сеансового, прикладного — перечислите для самопроверки в правильном порядке ), был быстро и безошибочно реализован.

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

Автор настоящей статьи твердо убежден, что ни один из тех, кто читает ее в настоящий момент времени, не думает, поднося ко рту ложку борща, бутерброд с икрой или стакан водки (рюмку коньяку — каждому свое). Все это получается само собой, рефлекторно. И читатель никогда не «промахнется», не пронесет вожделенное мимо рта. Так почему же нельзя также рефлекторно программировать?

Статья доктора наук Б. П. Кузнецова, изложенная «академически сдержанно», — крик души.

Однако после его [автоматного программирования] освоения возникает вопрос: как я мог программировать иначе? Автоматное программирование позволяет решать практически любые сложные циклические задачи с минимальными затратами на отладку.

Так и есть. Иные технологии программирования стоит рекомендовать лишь тем, кто склонен к садомазохизму.

Актуальность автоматного программирования

Почему же приемы автоматного программирования особенно актуальны сейчас? Имеют место две проблемы:

  1. непредсказуемое поведение кода программы, разработанной средствами RAD;
  2. угасание «культуры программирования».

Непредсказуемое поведение кода программы, разработанной средствами RAD

В начале девяностых появились средства быстрой разработки приложений (RAD — Rap >рисовать программы, перестаскивая в оконные формы визуальные компоненты из VCL.

Любой визуальный объект VCL характеризуется рядом свойств, методов и событий. Казалось бы, простой манипуляцией перечисленными атрибутами возможно заставлять разрабатываемую программу делать то, что требует от нее программист-разработчик. Не тут-то было.

Чарлз Калверт во вводной главе «Визуальное программирование — это RAD» своей книги «Delphi 2. Энциклопедия пользователя» честно признается:

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

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

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

Таким образом, ироничная сторона и огромное благо кое-кому выходят боком, ибо умалчиваемое поведение кода — коварство и тайная подлось средств RAD. Классический пример непредсказуемого поведения кода наглядно продемонстрировал поэт, «основоположник» объектно-ориентированного программирования. Поэт, который для нас — «всё» .

Мастер Йода рекомендует:  Где найти бесплатные текстуры для фона 15 отличных ресурсов

Примечание от 10.06.2014 г. — На днях поэту исполнилось бы 215 лет, но Яндекс из каких-то своих соображений отмечал 30-летие тетриса.

«Мой дядя — самых честных правил

Когда не в шутку занемог,

Он уважать себя заставил

И лучше выдумать не мог. »

Что представляет собой «дядя Пушкина» с позиции объектно-ориентированного программирования:

Каково же поведение TUncle? Как только значение свойства Health было изменено кодом программы (на целочисленное «занемог» ), «выстрелила» функция Respect («уважать себя заставил»). А должна ли была? Необязательно, поскольку имеется функция Think, посредством которой дядя мог бы выдумать что-нибудь и получше . Возможно, интерпретация не вполне корректна, зато наглядна.

Культура программирования

О культуре программирования можно сказать лишь то, что она, культура, медленно, но верно угасает. (Программисты-профессионалы советской школы смахнули, наверное, скупую мужскую слезу) . Сейчас все больше кодировщики, отличающиеся от программистов-разработчиков тем, что неспособны как поставить задачу, так и описать ее в программных документах.

Выводы


  1. поведение кода программы, разработанной исключительно средствами RAD, изначально непредсказуемо;
  2. чтобы поведение кода программы стало предсказуемым, следует научиться управлять поведением кода.

Как научиться управлять поведением кода программы?

Очень просто — приемом автоматного программирования — расстановкой «контрольных точек» с использованием оператора case — программной реализацией конечного автомата.

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

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

Лыжный кросс — расстановка контрольных точек

На рисунке выше изображена лыжная трасса. Точка 0 — старт и финиш, точки 1-7 — контрольные. В контрольных точках находятся судьи, фиксирующие время прохода и нагрудный номер лыжника.

При подобной организации сдачи норматива по лыжному кроссу лыжник оказывается «зажатым» контрольными точками в траекторию лыжной трассы. Если на финише выясняется, что лыжник не прошел хотя бы одну из контрольных точек — пересдача неминуема. А если «срез ать углы» между контрольными точками?

Однажды жизнь поставила перед выбором: либо километров десять по кривой, разбитой, но асфальтированной дороге, либо «срезать» и пройти напрямую, через лесок, километра три. Три километра «по прямой» оказались топью (дело было в Белоруссии) и были преодолены часа за четыре. Жизнь опровергла утверждение, что «кратчайшим расстоянием между двумя точками является прямая», и подтвердила иное — «суха теория, мой друг, но древо жизни пышно зеленеет».

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

Программно реализовать «сдачу норматива по лыжному кроссу» несложно в виде конечного автомата.

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

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

Конечный автомат реализован с помощью Delphi 7. На форму сброшены 8 кнопок, 0 именуется btnStart, остальные — cp1-cp7 (cp — control point). Нажатие кнопки эквивалентно проходу лыжником контрольной точки. Обработчиком событий OnClick всем восьми кнопкам назначена единая, заранее подготовленная процедура Release.

Метки Label1-3 подсказывают лыжнику-пользователю, какую кнопку придется нажимать следующей, показывают остаток времени до нажатия и результат. Фрагменты текста программы конечного автомата приведены ниже.

Текст программы конечного автомата

Как работает конечный автомат

Программа сразу после своего запуска отобразит сообщение пользователю — «Жми кнопку 0». Каковы могут быть ответные действия:

  1. пользователь с шаловливыми ручонками будет жать все, что угодно, кроме кнопки 0;
  2. послушный пользователь нажмет кнопку 0.

Реакция конечного автомата на шаловливые ручонки

Следует отметить, что непослушный пользователь может жать кнопки до скончания света, но ничего у него не выйдет. Нажатие любой из кнопок cp1-cp7 до нажатия кнопки btnStart конечный автомат попросту проигнорирует, поскольку в процедуре Release имеются строчки:

Во фрагменте кода конечного автомата отсутствует «ловушка» для переменной mode, равной 0. Код, расположенный внутри оператора case, выполняться не будет. Программа просто его обойдет. Указатель текущей строки кода в режиме отладчика (просто указатель) будет упрямо возвращаться к началу процедуры.

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

Как только пользователь нажмет кнопку 0 (btnStart), переменные режима mode и s_mode примут значения 1 и 0 соответственно. Указатель «провалится» в процедуру прохода «контрольной точки» и окажется внутри ветки 0 case s_mode of.

Кнопка btnStart станет недоступна и, вот она, фишка (. ), s_mode примет значение 1. Сие означает, что автомату присвоено следующее состояние. Весь остальной код, размещенный между begin-end, — шелуха, вернее, тот самый код, управлять выполнением которого призван конечный автомат. В первую очередь, сразу после begin, необходимо перевести автомат в следующее состояние. То, что автор сначала вставил код btnStart.Enabled:=True; — наглядный пример разгильдяйства и отсутствия культуры программирования .

Далее, после выполнения кода

конечный автомат будет ожидать события OnClick кнопки cp1, которой и соответствует состояние s_mode=1. Никакими уговорами пользователь не сможет заставить конечный автомат отреагировать на нажатие любой другой кнопки, кроме cp1, поскольку при неравенстве переменных o_mode («ожидаемой» кнопки) и s_mode (реально нажатой кнопки) указатель будет тупо возвращаться к началу процедуры — ждать события OnClick именно кнопки cp1.

Более того, указанный выше код конечного автомата запускает таймер. Таймер тихо отсчитывает пять секунд и останавливает «лыжный кросс», если пользователь так и не нажал кнопку cp1.

Указанным способом особенно удобно «строить» коммуникационные программы, реализующие протоколы обмена. Допустим, конечный автомат А из состояния 1 отправил байтовую последовательность (1) конечному автомату В, перешел в следующее состояние (2) и ждет четкого ответа (2) от автомата В. Автомат В может слать в линию все, что угодно (в течение пяти секунд). Но, если в течение пяти секунд автомат А не получит ожидаемого ответа (2) от автомата В — все, трындец. Таймер оповещает, что ожидаемый ответ от автомата В в заданном интервале времени не получен. Пользователь четко видит, где, на каком шаге конечного автомата произошел сбой при обмене данными. И принимает командирское решение.

Поскольку разъяснять словами все то, что «вытворяет» конечный автомат, довольно сложно, автор настоятельно рекомендует «погонять» конечный автомат в режиме пошаговой отладки. В режиме отладки следует закомментировать строку пуска таймера (Timer1.Enabled:=True;).

Модификация конечного автомата

Можно «поиграть» кодом конечного автомата: закомментировать часть кодов, поставить метку 1: напротив case s_mode of и добавить во все ветки, кроме крайней, goto 1.

Оператор goto, выполняющий безусловный переход к метке 1, многие программеры готовы «порвать, как Тузик тряпку» (искоренить из всех существующих языков программирования). Во многом они правы, но как быть без goto в конечном автомате? Может, кто знает, и готов поделиться соображениями? Уж лучше искоренили бы условный оператор if. Именно в операторе if (then, else) автор статьи видит причины всех программерских проблем, бед и неудач.

При внесенных в код изменениях конечный автомат последовательно «прогонит» указатель по веткам программы и остановится, ожидая очередного нажатия кнопки 0. Иными словами, конечный автомат после «пинка» пользователя самостоятельно пройдет все ветки программы, все контрольные точки, которые явно указал программист и, как все нормальные автоматы, вернется в свое исходное состояние.

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

Такой прогон удобно смотреть средствами отладки.

Примечание — После end; в программу стоит добавить оператор else, который позволит обрабатывать тупиковые ситуации.

Выводы

Конечный автомат работает по принципу «шаг в сторону — расстрел» (пересдача нормативов по лыжному кроссу). «Увильнуть» или «схитрить» конечный автомат не даст ни пользователю (исходный вариант кода), ни самой программе (модифицированный вариант кода). Автомат вынудит и того, и другого пройти «контрольные точки» именно так, как расписал программист.

Код конечного автомата изобилует ветвлениями, но ветвлений — логических структур «выбор» — в явном виде как будто бы и нет. Оператор case делает текст программы настолько «прозрачным», что на вопрос «а что будет, если» любой ткнет пальцем и попадет в самую точку. А насколько «прозрачна» конструкция if a>0 then b:=0 else if a b then (и так далее. )? Это к вопросу о культуре программирования — написанию легко читаемого кода.

Код конечного автомата взаимно -ортогонален. При модификации кода, при добавлении в код новых case-фрагментов изменять исходный код не потребуется. Программа не «поползет» — снижается вероятность ошибок при кодировании.

Заключение

Коль скоро было упомянуто о Пушкине, грех не вспомнить о Маяковском, предвосхитившем «рождение» оператора case (но без его фирменной «лесенки»).

«От вороны карапуз

Мальчик этот просто трус.

Это очень плохо.

Этот, хоть и сам с вершок,

спорит с грозной птицей.

Храбрый мальчик, хорошо,

в жизни пригодится».

Вот, что получается:

case мальчик of

Теперь, когда из примеров стало ясно, как конечный автомат управляет поведением кода программы, можно смело приступать к чтению статей профессора Б. П. Кузнецова и к разбору «произвольных циклических алгоритмов, представленных в виде графа переходов конечного автомата» . Удачи!

Связь по эл. почте admin @ tdocs . su (без пробелов), тел. +7-967-044-84-77 или в форме Контакты.

Copyright © «Техническая документация» 2008. Заимствуйте наши материалы с блеском! При воспроизведении материалов портала обязательна установка активной гиперссылки на источник — страницу с этой публикацией на tdocs.su.

Связь по эл. почте admin @ tdocs . su (без пробелов), тел. +7-967-044-84-77 или в форме Контакты.

Техническая документация

разработка техдокументации

Автоматное программирование для начинающих

В рунете лежит великолепная, но трудная для начинающих статья Б. П. Кузнецова «Психология автоматного программирования». Для специалистов не секрет, что знание принципов автоматного программирования дает возможность почти бездумно (и безошибочно), «пальцами» писать программы высочайшего уровня сложности. Редакция от 20.06.2020.

Автоматное программирование для начинающих

Создан 29.05.2005 9:49:02

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

Теорию автоматов преподают не везде. В технических ВУЗах преподают эту теорию применительно к синтезу цифровой аппаратуры, но не применительно к программированию (Такие выводы сделаны моим коллегой Шалыто А. А. для ведущих Питерских ВУЗов).

Автор прав. К сожалению, теория конечных автоматов и формальных языков читалась далеко и не в каждом московском ВУЗе. Автору настоящей статьи, выпускнику факультета электронной техники МЭИ, теория сия не читалась тоже. О существовании теории конечных автоматов было вскользь упомянуто в курсе цифровой схемотехники.

Жизнь — штука тонкая. Многим, кто окончил технические ВУЗы в начале (середине) восьмидесятых, пришлось не единожды менять область деятельности. Схемотехник вдруг начинал заниматься тонкопленочной технологией производства интегральных схем, специалист по электровакуумным приборам «вклинивался» в микропроцессорную схемотехнику. Выручало полученное в советских ВУЗах «широкое» образование, «ничего обо всем». Спасибо дорогому Леониду Ильичу за наше счастливое детство .

Автора настоящей статьи, как и «других похожих», жизнь (году в 1994-ом) вынудила забросить любимое «паяло» и погрузиться в разработку программ. По мере усложнения задач логики, здравого смысла, ВУЗовских знаний и навыков программирования, полученных самостоятельно, стало не хватать. Нехватка особенно сказывалась при разработке «коммуникационных» программ, реализации протоколов обмена данными. Организация взаимодействия пары модемов, обменивающихся данными по телефонной линии, казалась (в те времена) автору задачей почти неразрешимой.


Помощь подоспела вовремя со стороны старших товарищей, выпускников ВМиК МГУ, посвятивших автора настоящей статьи в основы теории конечных автоматов и показавших примеры реализации указанной теории на практике (одним из них — по странному стечению обстоятельств — был тоже Кузнецов, но другой). Достаточно сложный протокол обмена данными, работающий «поверх» протоколов физического и вышележащих уровней (транспортного, сетевого, сеансового, прикладного — перечислите для самопроверки в правильном порядке ), был быстро и безошибочно реализован.

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

Автор настоящей статьи твердо убежден, что ни один из тех, кто читает ее в настоящий момент времени, не думает, поднося ко рту ложку борща, бутерброд с икрой или стакан водки (рюмку коньяку — каждому свое). Все это получается само собой, рефлекторно. И читатель никогда не «промахнется», не пронесет вожделенное мимо рта. Так почему же нельзя также рефлекторно программировать?

Статья доктора наук Б. П. Кузнецова, изложенная «академически сдержанно», — крик души.

Однако после его [автоматного программирования] освоения возникает вопрос: как я мог программировать иначе? Автоматное программирование позволяет решать практически любые сложные циклические задачи с минимальными затратами на отладку.

Так и есть. Иные технологии программирования стоит рекомендовать лишь тем, кто склонен к садомазохизму.

Актуальность автоматного программирования

Почему же приемы автоматного программирования особенно актуальны сейчас? Имеют место две проблемы:

  1. непредсказуемое поведение кода программы, разработанной средствами RAD;
  2. угасание «культуры программирования».

Непредсказуемое поведение кода программы, разработанной средствами RAD

В начале девяностых появились средства быстрой разработки приложений (RAD — Rap >рисовать программы, перестаскивая в оконные формы визуальные компоненты из VCL.

Любой визуальный объект VCL характеризуется рядом свойств, методов и событий. Казалось бы, простой манипуляцией перечисленными атрибутами возможно заставлять разрабатываемую программу делать то, что требует от нее программист-разработчик. Не тут-то было.

Чарлз Калверт во вводной главе «Визуальное программирование — это RAD» своей книги «Delphi 2. Энциклопедия пользователя» честно признается:

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

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

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

Таким образом, ироничная сторона и огромное благо кое-кому выходят боком, ибо умалчиваемое поведение кода — коварство и тайная подлось средств RAD. Классический пример непредсказуемого поведения кода наглядно продемонстрировал поэт, «основоположник» объектно-ориентированного программирования. Поэт, который для нас — «всё» .

Примечание от 10.06.2014 г. — На днях поэту исполнилось бы 215 лет, но Яндекс из каких-то своих соображений отмечал 30-летие тетриса.

«Мой дядя — самых честных правил

Когда не в шутку занемог,

Он уважать себя заставил

И лучше выдумать не мог. »

Что представляет собой «дядя Пушкина» с позиции объектно-ориентированного программирования:

Каково же поведение TUncle? Как только значение свойства Health было изменено кодом программы (на целочисленное «занемог» ), «выстрелила» функция Respect («уважать себя заставил»). А должна ли была? Необязательно, поскольку имеется функция Think, посредством которой дядя мог бы выдумать что-нибудь и получше . Возможно, интерпретация не вполне корректна, зато наглядна.

Культура программирования

О культуре программирования можно сказать лишь то, что она, культура, медленно, но верно угасает. (Программисты-профессионалы советской школы смахнули, наверное, скупую мужскую слезу) . Сейчас все больше кодировщики, отличающиеся от программистов-разработчиков тем, что неспособны как поставить задачу, так и описать ее в программных документах.

Выводы

  1. поведение кода программы, разработанной исключительно средствами RAD, изначально непредсказуемо;
  2. чтобы поведение кода программы стало предсказуемым, следует научиться управлять поведением кода.

Как научиться управлять поведением кода программы?

Очень просто — приемом автоматного программирования — расстановкой «контрольных точек» с использованием оператора case — программной реализацией конечного автомата.

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

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

Лыжный кросс — расстановка контрольных точек

На рисунке выше изображена лыжная трасса. Точка 0 — старт и финиш, точки 1-7 — контрольные. В контрольных точках находятся судьи, фиксирующие время прохода и нагрудный номер лыжника.

При подобной организации сдачи норматива по лыжному кроссу лыжник оказывается «зажатым» контрольными точками в траекторию лыжной трассы. Если на финише выясняется, что лыжник не прошел хотя бы одну из контрольных точек — пересдача неминуема. А если «срез ать углы» между контрольными точками?

Однажды жизнь поставила перед выбором: либо километров десять по кривой, разбитой, но асфальтированной дороге, либо «срезать» и пройти напрямую, через лесок, километра три. Три километра «по прямой» оказались топью (дело было в Белоруссии) и были преодолены часа за четыре. Жизнь опровергла утверждение, что «кратчайшим расстоянием между двумя точками является прямая», и подтвердила иное — «суха теория, мой друг, но древо жизни пышно зеленеет».

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

Программно реализовать «сдачу норматива по лыжному кроссу» несложно в виде конечного автомата.

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

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

Конечный автомат реализован с помощью Delphi 7. На форму сброшены 8 кнопок, 0 именуется btnStart, остальные — cp1-cp7 (cp — control point). Нажатие кнопки эквивалентно проходу лыжником контрольной точки. Обработчиком событий OnClick всем восьми кнопкам назначена единая, заранее подготовленная процедура Release.

Метки Label1-3 подсказывают лыжнику-пользователю, какую кнопку придется нажимать следующей, показывают остаток времени до нажатия и результат. Фрагменты текста программы конечного автомата приведены ниже.

Текст программы конечного автомата

Как работает конечный автомат

Программа сразу после своего запуска отобразит сообщение пользователю — «Жми кнопку 0». Каковы могут быть ответные действия:

  1. пользователь с шаловливыми ручонками будет жать все, что угодно, кроме кнопки 0;
  2. послушный пользователь нажмет кнопку 0.

Реакция конечного автомата на шаловливые ручонки

Следует отметить, что непослушный пользователь может жать кнопки до скончания света, но ничего у него не выйдет. Нажатие любой из кнопок cp1-cp7 до нажатия кнопки btnStart конечный автомат попросту проигнорирует, поскольку в процедуре Release имеются строчки:

Во фрагменте кода конечного автомата отсутствует «ловушка» для переменной mode, равной 0. Код, расположенный внутри оператора case, выполняться не будет. Программа просто его обойдет. Указатель текущей строки кода в режиме отладчика (просто указатель) будет упрямо возвращаться к началу процедуры.

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

Как только пользователь нажмет кнопку 0 (btnStart), переменные режима mode и s_mode примут значения 1 и 0 соответственно. Указатель «провалится» в процедуру прохода «контрольной точки» и окажется внутри ветки 0 case s_mode of.

Кнопка btnStart станет недоступна и, вот она, фишка (. ), s_mode примет значение 1. Сие означает, что автомату присвоено следующее состояние. Весь остальной код, размещенный между begin-end, — шелуха, вернее, тот самый код, управлять выполнением которого призван конечный автомат. В первую очередь, сразу после begin, необходимо перевести автомат в следующее состояние. То, что автор сначала вставил код btnStart.Enabled:=True; — наглядный пример разгильдяйства и отсутствия культуры программирования .

Далее, после выполнения кода

конечный автомат будет ожидать события OnClick кнопки cp1, которой и соответствует состояние s_mode=1. Никакими уговорами пользователь не сможет заставить конечный автомат отреагировать на нажатие любой другой кнопки, кроме cp1, поскольку при неравенстве переменных o_mode («ожидаемой» кнопки) и s_mode (реально нажатой кнопки) указатель будет тупо возвращаться к началу процедуры — ждать события OnClick именно кнопки cp1.

Более того, указанный выше код конечного автомата запускает таймер. Таймер тихо отсчитывает пять секунд и останавливает «лыжный кросс», если пользователь так и не нажал кнопку cp1.

Указанным способом особенно удобно «строить» коммуникационные программы, реализующие протоколы обмена. Допустим, конечный автомат А из состояния 1 отправил байтовую последовательность (1) конечному автомату В, перешел в следующее состояние (2) и ждет четкого ответа (2) от автомата В. Автомат В может слать в линию все, что угодно (в течение пяти секунд). Но, если в течение пяти секунд автомат А не получит ожидаемого ответа (2) от автомата В — все, трындец. Таймер оповещает, что ожидаемый ответ от автомата В в заданном интервале времени не получен. Пользователь четко видит, где, на каком шаге конечного автомата произошел сбой при обмене данными. И принимает командирское решение.

Поскольку разъяснять словами все то, что «вытворяет» конечный автомат, довольно сложно, автор настоятельно рекомендует «погонять» конечный автомат в режиме пошаговой отладки. В режиме отладки следует закомментировать строку пуска таймера (Timer1.Enabled:=True;).

Модификация конечного автомата

Можно «поиграть» кодом конечного автомата: закомментировать часть кодов, поставить метку 1: напротив case s_mode of и добавить во все ветки, кроме крайней, goto 1.

Оператор goto, выполняющий безусловный переход к метке 1, многие программеры готовы «порвать, как Тузик тряпку» (искоренить из всех существующих языков программирования). Во многом они правы, но как быть без goto в конечном автомате? Может, кто знает, и готов поделиться соображениями? Уж лучше искоренили бы условный оператор if. Именно в операторе if (then, else) автор статьи видит причины всех программерских проблем, бед и неудач.

При внесенных в код изменениях конечный автомат последовательно «прогонит» указатель по веткам программы и остановится, ожидая очередного нажатия кнопки 0. Иными словами, конечный автомат после «пинка» пользователя самостоятельно пройдет все ветки программы, все контрольные точки, которые явно указал программист и, как все нормальные автоматы, вернется в свое исходное состояние.

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

Такой прогон удобно смотреть средствами отладки.

Примечание — После end; в программу стоит добавить оператор else, который позволит обрабатывать тупиковые ситуации.

Выводы


Конечный автомат работает по принципу «шаг в сторону — расстрел» (пересдача нормативов по лыжному кроссу). «Увильнуть» или «схитрить» конечный автомат не даст ни пользователю (исходный вариант кода), ни самой программе (модифицированный вариант кода). Автомат вынудит и того, и другого пройти «контрольные точки» именно так, как расписал программист.

Код конечного автомата изобилует ветвлениями, но ветвлений — логических структур «выбор» — в явном виде как будто бы и нет. Оператор case делает текст программы настолько «прозрачным», что на вопрос «а что будет, если» любой ткнет пальцем и попадет в самую точку. А насколько «прозрачна» конструкция if a>0 then b:=0 else if a b then (и так далее. )? Это к вопросу о культуре программирования — написанию легко читаемого кода.

Код конечного автомата взаимно -ортогонален. При модификации кода, при добавлении в код новых case-фрагментов изменять исходный код не потребуется. Программа не «поползет» — снижается вероятность ошибок при кодировании.

Заключение

Коль скоро было упомянуто о Пушкине, грех не вспомнить о Маяковском, предвосхитившем «рождение» оператора case (но без его фирменной «лесенки»).

«От вороны карапуз

Мальчик этот просто трус.

Это очень плохо.

Этот, хоть и сам с вершок,

спорит с грозной птицей.

Храбрый мальчик, хорошо,

в жизни пригодится».

Вот, что получается:

case мальчик of

Теперь, когда из примеров стало ясно, как конечный автомат управляет поведением кода программы, можно смело приступать к чтению статей профессора Б. П. Кузнецова и к разбору «произвольных циклических алгоритмов, представленных в виде графа переходов конечного автомата» . Удачи!

Связь по эл. почте admin @ tdocs . su (без пробелов), тел. +7-967-044-84-77 или в форме Контакты.

Copyright © «Техническая документация» 2008. Заимствуйте наши материалы с блеском! При воспроизведении материалов портала обязательна установка активной гиперссылки на источник — страницу с этой публикацией на tdocs.su.

Связь по эл. почте admin @ tdocs . su (без пробелов), тел. +7-967-044-84-77 или в форме Контакты.

Конечные автоматы в чистых функциональных языках программирования.
Автоматы и Haskell

Авторы: Я. М. Малаховски
А. А. Шалыто
СПБГУ ИТМО
Источник: RSDN Magazine #3-2009

Опубликовано: 07.02.2010
Исправлено: 10.12.2020
Версия текста: 1.0

Введение

Реализация конечных автоматов [1] рассматривалась на форуме и страницах журнала RSDN (например, [2]). Не раз освещались также вопросы, связанные с программированием на функциональных языках программирования ([3], [4]). Однако совместное использование этих подходов не рассматривалось.

В теории конечных автоматов существуют два класса [1]: абстрактные и структурные автоматы. Абстрактные автоматы обычно используются при разработке систем генерации парсеров по контекстно-свободным грамматикам и регулярным выражениям (например, [5], [6]). Функции переходов в таких задачах обычно строятся не по диаграммам состояний, а по множеству порождающих правил.

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

Основное отличие чистых функциональных программ от императивных состоит в том, что в чистых функциональных языках отсутствуют побочные эффекты, а следовательно и переменные, в том смысле, в котором этот термин используется в императивных языках. В то же время, состояние автомата в императивных программах обычно представлено полем класса (если используется объектно-ориентированное программирование) или глобальной переменной. Из изложенного следует, что в чистых функциональных языках программирования (например, Haskell [7]) не удается непосредственно применять методы, используемые при реализации конечных автоматов на императивных языках программирования (например, C++ [8]).

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

Реализация функций переходов на императивных и функциональных языках

Рассмотрим следующий пример: пусть требуется реализовать счетный триггер, реагирующий на события. Другими словами, требуется построить конечный автомат с двумя состояниями, кодируемыми нулем и единицей, который управляется кнопкой. Каждое нажатие кнопки порождает событие e. К выходу z конечного автомата подключена лампа. Каждое событие e переводит автомат в состояние (1 − y), где y – текущее состояние. При этом переменная состояния одновременно является выходной переменной (z = y). Таким образом, каждое нажатие кнопки будет приводить то к включению лампы, то к ее выключению. Диаграмма состояний рассматриваемого триггера представлена на рисунке 1.

Рисунок 1. Диаграмма состояний счетного триггера.

Приведем одну из возможных реализаций этого автомата на языке C:

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

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

При использовании языка Haskell компилятор может не только проверить, что все элементы функции переходов корректно типизированы, но и проверить также полноту и непротиворечивость реализации функции переходов. Например, если определить лишнюю ветку в функции gotEvent, как в следующем листинге:

то компилятор выдаст предупреждение.

Отметим также, что рассмотренная реализация функции переходов при помощи pattern matching не является единственной и вместо неё можно использовать конструкцию case, например, так:

Мастер Йода рекомендует:  10 лучших видеокурсов для изучения Linux

Последовательности событий

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

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

Отметим, что новая версия функции applyEvents является левой сверткой (одна из стандартных операций функционального программирования) списка событий по функции переходов. Поэтому можно заменить всё определение функции applyEvents на applyEvents = foldl.

Последовательности событий и монады

Одной из наиболее значимых встроенных конструкций языка Haskell являются монады. С их помощью, например, осуществляется ввод-вывод, который не нарушает функциональные основы языка. О монадах можно думать, как о способе объединения последовательности действий – в некотором смысле способ «эмулировать» императивное программирование в рамках функционального. Более подробно о монадах можно прочитать в статье [4]. Из сказанного не следует, что монады невозможно реализовать в других функциональных языках программирования, однако в Haskell они используются повсеместно.

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

Реализуем монаду FSM , предназначенную для манипуляции состояниями, а также различные вспомогательные функции и типы:

Можно заметить, что монада FSM очень похожа на стандартную монаду State , однако, проигнорировав это сходство, реализуем счетный триггер, используя код из предыдущего листинга:

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

Однако вдумчивый читатель заметит, что это всё – переливание из пустого в порожнее.

Дело в том, что при реализации абстрактных автоматов, как правило, вообще не требуется явная функция переходов, поскольку монада для абстрактных автоматов представляет собой моноид («допустимый результат» или «недопустимое выражение»), а функция переходов строится неявно при помощи различных комбинаторов. Например, в библиотеке Parsec [6] проверка того, что выражение состоит из символа a или символа b, за которым следует символ с (регулярное выражение (a|b)c), может быть реализована так:

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

Таким образом, использование монад оправдано при реализации абстрактных автоматов, но привносит только дополнительные накладные расходы (синтаксические, и, возможно, вычислительные) при реализации структурных автоматов.

Вложенность

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

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

Следовательно, имеется два конечных автомата («устройство» и меню), причем второй вложен в первый. Автомат, описывающий «устройство», имеет три состояния: «Выключено», «Включено» и «Меню», а автомат, описывающий меню, два: «Выбран первый пункт меню» и «Выбран второй пункт меню». Панель «устройства» содержит четыре кнопки: «Включить-выключить», «Меню», «Вверх», «Вниз». Графы переходов системы представлены на рисунке 2.

Рисунок 2. Диаграммы состояний устройства и его меню. «O», «M», «U», «D» – кнопки включения-выключения, меню, вверх и вниз соответственно.

Общую часть листингов этого раздела вынесем в отдельный листинг:

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

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

Отметим, что это первый пример, реализующий выходные воздействия – посылка события автоматом устройства автомату меню. В данном случае функция переходов всей системы systemSwF реализует передачу сообщений между вложенным и внешним автоматами.

Выходные воздействия

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

В качестве примера реализации автомата с выходными воздействиями рассмотрим счетный триггер с четырьмя состояниями (рисунок 3).

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

События и состояния для этого триггера представлены в следующем листинге:

Один из вариантов реализации выходных воздействий – изменить функцию переходов так, чтобы она возвращала не только новое состояние автомата, но и список выходных воздействий некоторого типа. Это может быть как арифметический тип данных, представляющий собой множество возможных выходных воздействий, так и тип IO(). В этом случае ответственность за выполнение выходных воздействий лежит на той части кода, которая вызывает функцию переходов автомата. Достоинством данного подхода является его гибкость.

Следующий листинг демонстрирует данный подход:

Проблема реализации выходных воздействий может быть решена также модификацией функции переходов. При этом в качестве возвращаемого значения она будет иметь тип IO state, где state – тип состояния автомата, а сами выходные воздействия будут выполняться непосредственно в самой функции переходов:

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

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


Декомпозиция функции переходов

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

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

Функцию переходов можно представить, как некоторый набор состояний, где каждое из них содержит внутри себя всю свою логику (реакцию на входные воздействия). Каждое состояние можно получить путем параметризации константами некоторого шаблона. Таким образом, функцию переходов автомата можно декомпозировать в набор параметризованных состояний-шаблонов , где тело функции переходов принимает решение только о том, какому из шаблонов передать управление.

В следующем листинге представлен пример реализации декомпозиции функции переходов счетного триггера с четырьмя состояниями (рисунок 3):

Ограничением состояния-шаблона statePattern, которое используется в приведенном выше листинге, является то, что оно может быть использовано только для работы со строго определенным типом событий. Дело в том, что левая часть ветки оператора case (до стрелки) должна быть константой и не может быть представлена как аргумент шаблона.

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

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

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

Активные автоматы

Пусть состояние автомата содержит источники, при помощи некоторой операции над которыми можно получить следующее событие. Источниками могут быть как числовые идентификаторы (например, файловый дескриптор UNIX), так и ссылки на объекты в памяти, константные списки событий и т. п.

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

Есть два варианта решения данной проблемы:

  • ввести специальное выходное воздействие, означающее «завершить исполнение»;
  • ввести специальное состояние, попав в которое, поток завершается («конечное состояние»).

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

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

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

Реализуем эти утверждения в следующем библиотечном коде:

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

Поскольку у данного триггера источником является стандартный ввод, то структура, представляющая источники активного автомата, в данном примере – пустой кортеж.

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

Функции выходов также может потребоваться множество источников автомата, например, для того, чтобы найти файловый дескриптор клиента, которому следует отправить сообщение. Именно поэтому определение типа IOAutomata имеет вид, представленный в листинге с библиотечным кодом.

Внедрение

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

Заключение

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

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

Если рассмотреть случай, когда автомат задан следующим образом: , где:

  • S — множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма — наличие нескольких начальных (стартовых) состояний у автомата .

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.

Автоматы и регулярные языки

Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет — так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

Специализированные языки программирования

  • Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.

Разработка моделей с использованием конечных автоматов

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

Примечания

См. также

  • Автоматное программирование
  • Sequential Function Chart
  • Компилятор
  • Транслятор
  • Сети Петри
  • Секвенциальная логика (Последовательностная логика)
  • Таблица принятия решений

Ссылки

  • М. И. Дехтярь Введение в схемы, автоматы и алгоритмы
  • Open source генератор конечных автоматов на языках C++ и Java по XML файлам описания
  • Недетерминированные конечные автоматы
  • С. Ю. Подзоров Курс лекции по теории алгоритмов
  • Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109–188. — URL https://www.mathnet.ru/php/getFT.phtml?jrn >
В этой статье не хватает ссылок на источники информации.

Wikimedia Foundation . 2010 .

Смотреть что такое «Конечный автомат» в других словарях:

конечный автомат — КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. [https://www.morepc.ru/dict/] конечный автомат Спецификация последовательности… … Справочник технического переводчика

Конечный автомат — математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. По английски: Finite state machine См … Финансовый словарь


конечный автомат — baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… … Automatikos terminų žodynas

КОНЕЧНЫЙ АВТОМАТ — автомат, у к рого множество состояний, а также множество входных и выходных сигналов являются конечными. К. а. может быть моделью технич. устройства (ЭВМ, релейное устройство) либо биол. системы (идеализир. нервная система животного). Важными… … Большой энциклопедический политехнический словарь

конечный автомат в модульном исполнении — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite modular automaton … Справочник технического переводчика

конечный автомат доступности — (МСЭ Т Y.1711). [https://www.iks media.ru/glossary/index.html?gloss >Справочник технического переводчика

Конечный автомат с памятью — Конечный автомат с памятью математическая модель устройства, поведение которого зависит как от входных условий, так и от предыдущего состояния. Для описания конечного автомата с памятью используются языки операторных схем, регулярных… … Википедия

детерминированный конечный автомат — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite deterministic automaton … Справочник технического переводчика

Автомат Мура — (автомат второго рода) в теории вычислений конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван … Википедия

Конечный — Содержание 1 Конечный 2 Конечная 3 Конечные 4 Фамилия … Википедия

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

Элементы теории автоматов

План:

1. Понятие автомата, принцип работы автомата

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

3. Общие задачи теории автоматов

Теоретические сведения

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

Понятие автомата, принцип работы автомата

Понятие автомат[1] рассматривается в двух аспектах:

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

2. Автомат – математическое понятие, обозначающее математическую модель реальных технических устройств. Автомат это абстрактное устройство, непонятно почему и как оно работает и, вообще, почему оно может работать. В этом аспекте автомат есть «черный ящик», который теоретически способен проводить некоторые действия. С точки зрения математики, абсолютно неважно что, как и почему производит те или иные действия.

Любой автомат должен иметь некоторое количество входов, некоторое количество выходов и некоторое количество внутренних состояний.

Алгебраическая теория автоматов является разделом теоретической кибернетики, который изучает дискретные автоматы с абстрактной алгебраической точки зрения.

Общая теория автоматов содержит различные подразделы. В зависимости от предмета изучения она делится на абстрактную теорию автоматов и структурную теорию автоматов.

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

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

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

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

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

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

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

Считается, что первым программным устройством, созданным человеком, были часы. Часовые механизмы с помощью пружины, приводящей в действие шестеренки и кулачковые механизмы, зубчатые колеса и рычаги, осуществляют ряд определенных действий. Примером такого часового механизма могут быть знаменитые часы на Центральном театре кукол в Москве, где он приводит в действие двенадцать сказочных героев, расположенных на циферблате[2].

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

1. Немецкий философ и алхимик Альберт Великий с 1216 по 1246 г., создавал «железного» слугу — автомат, который выполнял в доме обязанности привратника.

2. Астроном Иоганн Мюллер (Региамонтан) (1436-1476) создал механического орла, который приветствовал наклоном головы и движением крыльев въезд в Нюрнберг императора священной Римской империи Максимилиана II.

3. Механик Жак де Вакансон (1709-1782) – автор первого в мире автоматического ткацкого станка. Он создал образ механической утки, точной копии своего живого двойника — плавала, чистила перья, глотала с ладони зерна. Его механический флейтист, исполнявший одиннадцать музыкальных пьес, поражал людей, живших в те далекие годы.

4. Русский изобретатель 19 в. А. М. Гамулецкий создал целый механический кабинет, в котором было множество сконструированных им автоматов. Здесь в том числе была и говорящая голова чародея и амур, играющий на арфе, которые поражали воображение современников.

5. Первый примитивный арифмометр сконструировал в 1641 г. Блез Паскаль. Толчком для открытия были мучения его отца – налогового, инспектора, который днями и ночами работал с большими вычислениями. Изобретя арифмометр, восемнадцати летний сын избавил отца от сложных вычислений, а миру подарил первый калькулятор, производящий сложение и вычитание чисел.

6. Первый шахматный автомат был построен в 1890 г. испанским инженером Торресом Кеведо. Такой автомат мог разыграть лишь ладейный эндшпиль (король и ладья против короля).

7. Первую вычислительную машину с автоматическим управлением создал Чарльз Баббедж в 1822 г. Он спроектировал арифмометр, который имел запоминающие и арифметические устройства. Эти устройства стали прототипами аналогичных устройств современным ЭВМ.

Виды автоматов.

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

Любой автомат имеет собственные базовые множества, которые включают в себя:алфавит входа, алфавит выхода, множество состояний автомата.

Характерной особенностью конечного автомата является наличие памяти, которая определяет состояние автомата в зависимости от времени. Внешним проявлением различных состояний автомата является его реакция на однотипные воздействия (сигналы).

В работе конечных цифровых автоматов важным понятием является время.

Автоматы можно классифицировать по различным признакам.

1. По виду деятельности автоматы делятся на: информационные, управляющие и вычислительные.

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

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

К вычислительным автоматам относятся микрокалькуляторы, процессоры в ЭВМ и иные устройства, выполняющие вычисления.

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

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

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

4. Абстрактные автоматы —отображающие множество слов входного алфавита Х во множество слов выходного алфавита Y.

Абстрактный автомат есть:

Алгоритм действия некоторого преобразования кодовых последовательностей,

Закон преобразования входного алфавита в выходной.

5. Синхронные и асинхронные автоматы. В зависимости от того, одновременно или последовательно принимаются входной сигнал и сигнал смены состояний, автоматы делятся насинхронные и асинхронные автоматы.

В синхронных автоматах продолжительность входных сигналов и время переходов согласовано между собой. Они используются в вычислительных комплексах, АСУ и т.д.

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

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

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

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

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

В вероятностных автоматах эта зависимость связана еще и с некоторым случайным выбором.

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

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

Математическая модель цифрового автомата с одним входом задается пятью объектами:

X- конечное множество входных символов, входной алфавит:

Y- конечное множество выходных символов, выходной алфавит:

конечное множество состояний автомата:

δ(q, х) — функция перехода автомата из одного состояния в другое: (Q х X) ®Q;

функция выхода автомата: (Q x Х) ® Y.

Таким образом, конечный автомат С= (X, Q, У, δ, λ.) определяется рекуррентными соотношениями

q(0) = q, q(t + I) = δ (g(t), х(t)), y(t) = λ (g(t), х(t)),

t- дискретизированный момент времен или это есть образ монотонной функции t:. Т ® N, причем Т — обычное непрерывное время, N — множество натуральных чисел.

Все время работы Т разбивается на конечное число интервалов, на границе которых происходит изменение состояния автомата. При этом t(Г) – показывает число изменений, произошедших до момента времени Г.

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

9. Синхронные автоматы делятся на автоматы Мили и автоматы Мура. В зависимости от способа организации функции выхода синхронные автоматы делятся на автоматы Мили (автоматы I рода) и автоматы Мура(автоматы II рода).

В автоматах Мили— выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент времени (t-1). Математической моделью таких автоматов служит система уравнений:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t-1), х(t)),

В автоматах Муравыходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени t. Математической моделью таких автоматов является система:

q(t) = δ (q(t-1), х(t)) и y(t) = λ (q(t)),

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

10. Комбинационные автоматы – есть автоматы, в которых выходной символ не зависит от его состояния и определяется лишь текущими входными символами, т.е. в этом автомате все состояния эквивалентны. В таком автомате вырождена функция перехода, она принципиально не важна и в процессе функционирования неизменна. Поэтому минимальный комбинационный автомат имеет лишь одно состояние.

11 Логическиеавтоматы – есть автоматы у которых входной алфавит состоит из 2 т двоичных наборов длины т, а выходной — из 2 n двоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.

Добавить комментарий