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

Хочу заметить что стимулом написания этого поста послужил цикл статей о SWITCH-технологии Владимира Татарчевского. Цикл статей называется «Применение SWITCH-технологии при разработке прикладного программного обеспечения для микроконтроллеров» Так что в этом статье я постараюсь по большей части привести пример рабочего кода и его описание.

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

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

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

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

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

Стили программирования.

«Стили программирования» — звучит как-то непонятно, ну да ладно. Что я хочу этим сказать?Представим, что человек никогда до этого не занимался программированием, то есть вообще полный чайник.

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

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

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

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

Void main(void) { initial_AL(); //инициализация периферии while(1) { Leds_BLINK(); //функция светодиодной мигалки signal_on(); //функция включения сигнала signal_off(); //функция выключения сигнала l=button(); //переменная отвечающая за нажатие кнопок switch(l) //В зависимости от величины переменной выполняется то или иное действие { case 1: { Deistvie1(); //Вместо функции может быть условный оператор Deistvie2(); //или еще несколько веток switch case Deistvie3(); Deistvie4(); Deistvie5(); }; case 2: { Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); }; . . . . . . . . } } }

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

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

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

2. Цикл + прерывания.

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

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

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

3. Автоматное программирование.

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

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

В грубом представлении это как выключатель освещения. Есть два состояния включено и выключено, и два условия включить и выключить. Ну а обо всем по порядку.

Реализация многозадачности в switch-технологии.

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

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

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

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

Система обмена сообщениями.

Разрулить многочисленные процессы и создать иллюзию многозадачности можно используя систему обмена сообщениями.

Допустим нам нужна программа в которой идет переключение светодиода. Вот у нас есть два автомата, назовем их LEDON -автомат ответственный за включение светодиода и автомат LEDOFF — автомат ответственный за выключение светодиода.

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

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

Int main(void) { INIT_PEREF(); //инициализация периферии (светодиоды) InitGTimers(); //инициализация таймеров InitMessages(); //инициализация механизма обработки сообщений InitLEDON(); //инициализация автомата LEDON InitLEDOFF(); //инициализация автомата LEDOFF SendMessage(MSG_LEDON_ACTIVATE); //активируем автомат LEDON sei(); //Разрешаем прерывания //Главный цикл программы while(1) { ProcessLEDON(); //итерация автомата LEDON ProcessLEDOFF(); //итерация автомата LEDOFF ProcessMessages(); //обработка сообщений }; }

В строках 3 -7 происходят различные инициализации поэтому нас это сейчас не особо интересует. А вот дальше происходит следующее: перед запуском главного цикла (while(1)), мы отправляем сообщение автомату

SendMessage(MSG_LEDON_ACTIVATE)

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

Небольшое отступление:

Сообщение имеет три состояния. А именно состояние сообщение может быть неактивно, установлено но неактивно и активное состояние.

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

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

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

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

Таймеры

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

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

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

Алгоритм будет следующим:

Можно кликнуть чтобы увеличить

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

1. Входим в состояние посредством принятия сообщения.

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

3. Отправляем сообщение следующему автомату.

4. Выход

В следующем входе все повторяется.

Программа по SWITCH-технологии. Три шага.

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

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

Программа будет у нас модульной и поэтому будет разбита на несколько файлов. Модули у нас будут следующие:

• Модуль основного цикла программы содержит файлы leds_blink.c, HAL.c, HAL.h
• Модуль таймеров содержит файлы timers.c, timers.h
• Модуль обработки сообщений содержит файлы messages.c, messages.h
  
• Модуль автомата 1 содержит файлы ledon.c, ledon.h
• Модуль автомата 2 содержит файлы ledoff.c , ledoff .h

Шаг 1.

Создаем проект и сразу подключаем к нему файлы наших статичных модулей:timers.c, timers.h, messages.c, messages.h.

Файл leds_blink.c модуля основного цикла прогарммы.

#include "hal.h" #include "messages.h" //модуль обработки сообщений #include "timers.h" //модуль таймеров //Прерывания по таймеру //############################################################################################ ISR(TIMER0_OVF_vect) // переход по вектору прерывания (переполнение таймера счетчика T0) { ProcessTimers(); //Обработчик прерываний от таймера } //########################################################################################### int main(void) { INIT_PEREF(); //инициализация переферии (светодиоды) InitGTimers(); //инициализация таймеров InitMessages(); //инициализация механизма обработки сообщений InitLEDON(); //инициализация автомата LEDON InitLEDOFF(); StartGTimer(TIMER_SEK); //Запуск таймера SendMessage(MSG_LEDON_ACTIVATE); //активируем автомат FSM1 sei(); //Разрешаем прерывания //Главный цикл программы while(1) { ProcessLEDON(); //итерация автомата LEDON ProcessLEDOFF(); ProcessMessages(); //обработка сообщений }; }

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

Со строчки int main (void) можно сказать начинается основная программа. И начинается она с инициализации всего и вся. Здесь инициализируем периферию, то есть задаем начальные значения портам ввода вывода компаратору и всему остальному содержимому контроллера. Все это делает функция INIT_PEREF, здесь ее запускаем, хотя основное ее тело находится в файле hal.c.

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

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

StartGTimer(TIMER_SEK); //Запуск таймера SendMessage(MSG_LEDON_ACTIVATE); //активируем автомат FSM1

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

Hal.h — это заголовочный файл модуля основного цикла программы.

#ifndef HAL_h #define HAL_h #include #include //Стандартная библиотека включающая в себя прерывания #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //компаратор #define ViklKomparator 1<

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

А вот файл Hal.c — это уже исполняемый файл, и как я уже упоминал, в нем содержится различный инициализации периферии.

#include "hal.h" void INIT_PEREF(void) { //Инициализация портов ввода-вывода //################################################################################### Komparator = ViklKomparator; //инициализация компаратора - выключение DDRD = 1<

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

Шаг 3.

Нам осталось написать модули конечных автоматов, в нашем случае автомата LEDON и автомата LEDOFF. Для начала приведу текст программы автомата зажигающего светодиод файл ledon.c.

//файл ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //переменная состояния void InitLEDON(void) { ledon_state=0; //здесь можно выполнить инициализацию других //переменных автомата при их наличии } void ProcessLEDON(void) { switch(ledon_state) { case 0: //неактивное состояние if(GetMessage(MSG_LEDON_ACTIVATE)) //если сообщение есть то оно будет принято { //и пойдет проверка таймера if(GetGTimer(TIMER_SEK)==one_sek) //если таймер засек 1сек то выполняем { StopGTimer(TIMER_SEK); PORTD = 1<

Здесь в первых строчках как всегда подключаются библиотеки и объявляются переменные. Далее у нас пошли уже функции, с которыми мы уже встречались. Это функция инициализации автомата InitLEDON и функция уже самого обработчика автомата ProcessLEDON.

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

Заголовочный файл для автомата будет еще проще:

//файл fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Здесь подключаем связующий файл hal.h а также указываем прототипы функций.

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

Все файлы проекта вы можете скачать вот по этой ссылке ====>>>ССЫЛКА .

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

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

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

С н/п Владимир Васильев

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Public class FSM { private var activeState:Function; // указатель на активное состояние автомата public function FSM() { } public function setState(state:Function) :void { activeState = state; } public function update() :void { if (activeState != null) { activeState(); } } }

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

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

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

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

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

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

Public class Ant { public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) { position = new Vector3D(posX, posY); velocity = new Vector3D(-1, -1); brain = new FSM(); // Начинаем с поиска листка. brain.setState(findLeaf); } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { } public function update():void { // Обновление конечного автомата. Эта функция будет вызывать // функцию активного состояния: findLeaf(), goHome() или runAway(). brain.update(); // Применение скорости для движения муравья. moveBasedOnVelocity(); } (...) }

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

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

Public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

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

Public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

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

Public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочек. brain.setState(findLeaf); } }

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

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

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

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

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

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

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

Public class StackFSM { private var stack:Array; public function StackFSM() { this.stack = new Array(); } public function update() :void { var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) { currentStateFunction(); } } public function popState() :Function { return stack.pop(); } public function pushState(state:Function) :void { if (getCurrentState() != state) { stack.push(state); } } public function getCurrentState() :Function { return stack.length > 0 ? stack : null; } }

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

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

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

Public class Ant { (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) { (...) brain = new StackFSM(); // Начинаем с поиска листка brain.pushState(findLeaf); (...) } /** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void { // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) <= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.popState(); } } (...) }

Вывод

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

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

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

Два наиболее распространенных способа конечного задания формального языка - это грамматики и автоматы. Автоматами в данном контексте называют математические модели некоторых вычислительных устройств. В этой лекции рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам. Более сильные вычислительные модели будут определены позже, в лекциях "10" , "14" и "15" . Термин "автоматный язык" закреплен за языками, распознаваемыми именно конечными автоматами, а не какими-либо более широкими семействами автоматов (например, автоматами с магазинной памятью или линейно ограниченными автоматами).

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

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

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

Другая серия результатов связана с возможностью сузить некоторый класс грамматик, не изменив при этом класс порождаемых ими языков. Обычно в таком случае грамматики из меньшего класса называются грамматиками в нормальной форме. В разделе 2.5 * формулируется результат такого типа для праволинейных грамматик. Сама эта теорема не представляет большого интереса, но аналогичные результаты, доказываемые позже для контекстно-свободных грамматик, используются во многих доказательствах и алгоритмах.

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

2.1. Недетерминированные конечные автоматы

Определение 2.1.1 . Конечный автомат ( finite automaton , finite -state machine) - это пятерка , где - конечный входной алфавит (или просто алфавит ) данного конечного автомата, и - конечные множества,

, . Элементы Q называются состояниями (state), элементы I - начальными (initial) состояниями, элементы F - заключительными или допускающими (final, accepting) состояниями. Если , то называется переходом (transition) из p в q , а слово x - меткой (label) этого перехода.

Пример 2.1.2 . Пусть Q = {1,2} , , I = {1} , F = {2} ,

Тогда - конечный автомат.

Замечание 2.1.3 . Конечные автоматы можно изображать в виде диаграмм состояний (state diagram) (иногда их называют диаграммами переходов (transition diagram)). На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Стрелка из p в q , помеченная словом x , показывает, что является переходом данного конечного автомата. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое допускающее состояние отмечается на диаграмме двойным кружком.

Пример 2.1.4 . На диаграмме изображен конечный автомат из примера 2.1.2.

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

Пример 2.1.6 . На диаграмме снова изображен конечный автомат из примера 2.1.2.

Определение 2.1.7 . Путь (path) конечного автомата - это кортеж , где и для каждого i . При этом q 0 - начало пути q n - конец пути n - длина пути w 1 ...w n - метка пути .

Замечание 2.1.8 . Для любого состояния существует путь . Его метка - , начало и конец совпадают.

Определение 2.1.9 . Путь называется успешным если его начало принадлежит I , а конец принадлежит F .

Пример 2.1.10 . Рассмотрим конечный автомат из примера 2.1.2. Путь является успешным. Его метка - baaab . Длина этого пути - 4.

Определение 2.1.11 . Слово w допускается (is accepted, is recognized) конечным автоматом M , если оно является меткой некоторого успешного пути.

Определение 2.1.12 . Язык, распознаваемый конечным автоматом M , - это язык L(M) , состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат M распознает ( recognizes , accepts) язык L(M) .

Замечание 2.1.13 . Если , то язык, распознаваемый конечным автоматом , содержит .

Пример 2.1.14 . Пусть , где Q = {1,2} , , I = {1} , F = {1,2} ,

Определение 2.1.15 . Два конечных автомата эквивалентны , если они распознают один и тот же язык.

Определение 2.1.16 . Язык L называется автоматным ( finite -state language), если существует конечный автомат, распознающий этот язык.

Замечание 2.1.17 . Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).

Пример 2.1.18 . Рассмотрим однобуквенный алфавит . При любых фиксированных и язык является автоматным.

Замечание 2.1.19 . Каждый конечный язык является автоматным.

Определение 2.1.20 . Состояние q достижимо (reachable) из состояния p , если существует путь, началом которого является p , а концом - q .

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

Пример 2.1.22 . Рассмотрим конечный автомат , где Q = {1,2,3,4} , , I = {1,2,4} , F = {1,3,4} ,

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

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

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

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

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

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

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

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

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

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

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

· начальным состоянием;

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

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

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

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

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

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

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

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

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

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

S = { A, Q, d, l,V },

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

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

терминалов);

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

(множество нетерминалов);

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

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

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

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

План:

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

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

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

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

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

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

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

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

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- конечное множество входных символов, входной алфавит:

Х= {x 1 (t), x 2 (t), …, x n (t)};

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

У={y 1 (t), y 2 (t), …, y n (t)};

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

Q= {q 0 (t), q 1 (t), q 2 (t), …, q n (t)}, q 0 - начальное состояние;

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

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

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

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

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

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

Примером дискретизации служит обычный кинематограф: время разбито на интервалы длительностью 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 двоичных наборов длины п. Для логических комбинационных автоматов функция выхода имеет вид системы п логических функций от т переменных.