Определение конечных автоматов. Конечные автоматы: преобразователи и распознаватели Конечные автоматы для чайников
алфавита : при i=1, ..., n . Число букв в этой последовательности называется длиной слова и обозначается |w| . Имеется одно специальное "пустое" слово длины 0. Будем обозначать его через На словах определена операция приписывания одного слова после другого, называемая конкатенацией : если слово w =w 1 ... w n , а слово v =v 1 ... v m , то их конкатенация - это слово w 1 ... w n v 1 ... v m длины n+m . Обычно знак конкатенации будем опускать и писать просто w v (по аналогии со знаком умножения в алгебре). Пустое слово - это единственное слово такое, что для любого слова w справедливо равенство . Операция конкатенации ассоциативна: для любых трех слов w, v и u , очевидно, имеет место равенство: (w v)u = w(v u) . Поэтому скобки при записи конкатенации нескольких слов будем опускать. Для представления нескольких конкатенаций одного и того же слова используют сокращенную "степенную форму" записи: . Например, a 3 b 4 c 2 - это сокращенная запись слова aaabbbbcc .Языком в алфавите называется произвольное множество слов этого алфавита. Язык , включающий все слова в алфавите (в том числе и пустое слово ), будем обозначать через .
Конечные автоматы часто используются для определения тех или иных свойств слов , т.е. для распознавания языков : автомат, распознающий некоторый язык L должен по произвольному слову w ответить на вопрос " ? ". Для решения такой задачи функция выходов может быть заменена на проверку того, в какое состояние переходит автомат после получения входного слова w - "принимающее" или "отвергающее".
Определение 4.3 . Детерминированный конечный автомат (ДКА) - распознаватель - это система вида
включающая следующие компоненты:
Функцию называют программой
автомата A
и задают как список из m n
команд
вида 
.
Удобно также задавать функцию с помощью описанной выше таблицы размера n x m , строки которой соответствуют состояниям из Q , а столбцы - символам из входного алфавита и в которой на пересечении строки q i и столбца a j стоит состояние .
Как и автоматы-преобразователи , автоматы- распознаватели можно представлять с помощью размеченных ориентированных графов, называемых диаграммами .
Определение 4.4
. Диаграмма ДКА
- это
ориентированный (мульти)граф D A =(Q, E)
с помеченными ребрами,
в котором выделена вершина- начальное
состояние
q 0
из каждой вершины
выходит ребер, помеченных символами
так, что для каждой и каждого символа имеется единственное ребро
из q
в вершину 
с меткой a
.
Скажем, что представленный последовательностью ребер путь p=e 1 e 2 ... e t в диаграмме несет слово w=w 1 w 2 ... w t , если w i - это метка ребра e i (1 >= i >= t) . Если q - начальная вершина (состояние) этого пути, а q" - его заключительная вершина, то будем говорить, что слово w переводит q в q" .
Работа конечного автомата-распознавателя состоит в чтении входного слова и изменению состояний в зависимости от его символов.
Определение 4.5 . Назовем конфигурацией ДКА произвольную пару вида (q, w) , в которой и .
На множестве конфигураций введем отношение перехода за один шаг :
Если , то положим для каждого : .
Через обозначим рефлексивное и транзитивное замыкание .
Содержательно, означает, что автомат A , начав работу в состоянии q на слове w=w 1 ... w l , через некоторое конечное число шагов 0 <= k <= l прочтет первые k символов слова w и перейдет в состояние q" , а w" =w k+1 ... w l - это непрочтенный остаток слова w .
Определение 4.6 . ДКА A распознает (допускает, принимает) слово w , если для некоторого
Т.е. после обработки слова w автомат переходит в принимающее состояние.
Язык L A , распознаваемый (допускаемый, принимаемый) автоматом A , состоит из всех слов , распознаваемых этим автоматом.
Результат работы автомата определяется по его конечному состоянию.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: , где:
Автомат начинает работу в состоянии q 0 , считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».
Конечные автоматы широко используются на практике, например в синтаксических , лексических анализаторах , и тестировании программного обеспечения на основе моделей .
Другие способы описания
- Диаграмма состояний (или иногда граф переходов ) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф , вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
- Таблица переходов - табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу - один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.
Детерминированность
Конечные автоматы подразделяются на детерминированные и недетерминированные.
Детерминированный конечный автомат
- Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.
- Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:
| Существуют переходы, помеченные пустой цепочкой ε | Из одного состояния выходит несколько переходов, помеченных одним и тем же символом |
|---|---|
Если рассмотреть случай, когда автомат задан следующим образом: , где:
Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата .
Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.
В силу последних двух замечаний, несмотря на бо́льшую сложность недетерминированных конечных автоматов, для задач, связанных с обработкой текста, преимущественно применяются именно НКА.
Автоматы и регулярные языки
Для автомата можно определить язык (множество слов) в алфавите Σ, который он представляет - так называются слова, при вводе которых автомат переходит из начального состояния в одно из состояний множества F.
Специализированные языки программирования
- Язык последовательных функциональных схем SFC (Sequential Function Chart) - графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).
В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.
Разработка моделей с использованием конечных автоматов
Конечные автоматы позволяют построить модели систем параллельной обработки, однако, чтобы изменить число параллельных процессов в такой модели требуется внести существенные изменения в саму модель. Кроме того, попытка разработки сложной модели на конечном автомате приведет к быстрому росту числа состояний автомата, что в итоге сделает разработку такой модели крайне утомительным занятием. Как было отмечено выше последнюю проблему можно решить, если использовать недетерминированный автомат.
Примечания
См. также
- Секвенциальная логика (Последовательностная логика)
Ссылки
- Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. - М.: ВИНИТИ, 1976. - Т. 13. - С. 109–188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
- Применение конечных автоматов для решения задач автоматизации
- Пример реализации конечного автомата на языке Python для фреймворка Django
Wikimedia Foundation . 2010 .
- Кейнс, Джон Мейнард
- Диаграмма состояний (теория автоматов)
Смотреть что такое "Конечный автомат" в других словарях:
конечный автомат - КА Вычислительная модель, описывающая автомат с конечным числом состояний. КА широко применяются в программировании, например в лексических анализаторах компиляторов. конечный автомат Спецификация последовательности… …
Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. По английски: 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). Тематики электросвязь, основные понятия EN availability state machineASM … Справочник технического переводчика
Конечный автомат с памятью - Конечный автомат с памятью математическая модель устройства, поведение которого зависит как от входных условий, так и от предыдущего состояния. Для описания конечного автомата с памятью используются языки операторных схем, регулярных… … Википедия
детерминированный конечный автомат - — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN finite deterministic automaton … Справочник технического переводчика
Автомат Мура - (автомат второго рода) в теории вычислений конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван … Википедия
Сегодня мы поговорим о автоматах, но отнюдь не тех что держат в руках солдаты российской армии. Речь пойдет о таком интересном стиле программирования микроконтроллеров как автоматное программирование. Точнее это даже не стиль программирования а целая концепция, благодаря которой программист микроконтроллеров может значительно облегчить свою жизнь. Благодаря которой многие задачи представленные перед программистом решаются гораздо легче и проще, избавляя программиста от головной боли. Кстати автоматное программирование зачастую называют 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 Как вы могли заметить этот файл по своей сути не содержит ни строчки исполняемого кода — это все макроподстановки и подключение библиотек. Наличие этого файла просто очень хорошо облегчает жизнь, он улучшает наглядность. А вот файл 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 а также указываем прототипы функций. Файл ответственный за выключение светодиода будет выглядеть практически также только в зеркальном отражении, так, что здесь я его выводить не буду — неохота 🙂 Все файлы проекта вы можете скачать вот по этой ссылке ====>>>ССЫЛКА
. Вот всего три шага и наша программа приобрела законченный вид а значит на этом моя миссия на сегодня закончена и пора закругляться. Мне кажется что информация приведенная в этой статье будет для вас очень полезно. Но настоящую пользу она принесет только тогда, когда вы будете применять это знание на практике. Кстати я запланировал ряд интересных проектов которые будут особенно интересны, так что обязательно подпишитесь на новые статьи
. Также я планирую делать рассылку дополнительных материалов, поэтому многие уже подписываются через основную страницу сайта. Подписаться можно и здесь. Ну теперь у меня действительно все, поэтому я желаю вам удачи, прекрасного настроения и до новых встреч. С н/п Владимир Васильев Аннотация:
В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам, определяются понятия конечного автомата, недетерминированного конечного автомата и распознаваемого конечным автоматом языка. Приведены практические примеры и упражнения для закрепления материала
Два наиболее распространенных способа конечного задания
формального языка - это грамматики и автоматы.
Автоматами в данном контексте называют математические модели
некоторых вычислительных устройств.
В этой лекции рассматриваются конечные
автоматы,
соответствующие в иерархии Хомского
праволинейным грамматикам.
Более сильные вычислительные модели
будут определены позже,
в лекциях "10" , "14"
и "15" .
Термин "автоматный язык" закреплен за языками,
распознаваемыми именно конечными автоматами,
а не какими-либо более
широкими семействами автоматов
(например, автоматами с магазинной памятью или
линейно ограниченными автоматами). В разделе 2.1 определяются понятия
конечного автомата
(для ясности такой автомат
можно называть
недетерминированным конечным автоматом)
и
распознаваемого конечным автоматом языка.
В следующем разделе дается другое,
но эквивалентное первому определение
языка, распознаваемого конечным автоматом.
Оно не является необходимым для дальнейшего изложения,
но именно это определение
поддается обобщению
на случаи автоматов других типов. В разделе 2.3 доказывается, что
тот же класс
автоматных языков можно получить, используя
лишь конечные
автоматы специального вида
(они читают на каждом такте ровно один символ
и имеют ровно одно начальное состояние).
Во многих учебниках конечными автоматами
называют именно такие автоматы. Целую серию классических результатов теории формальных языков
составляют теоремы о точном соответствии некоторых классов
грамматик некоторым классам автоматов.
Первая теорема из этой серии, утверждающая, что
праволинейные грамматики порождают в точности автоматные языки,
доказывается в разделе 2.4. Другая серия результатов связана с возможностью
сузить некоторый класс
грамматик, не изменив при этом
класс
порождаемых ими языков.
Обычно в таком случае грамматики из меньшего класса
называются грамматиками в нормальной форме.
В разделе 2.5 *
формулируется результат такого типа
для праволинейных грамматик.
Сама эта теорема не представляет большого интереса,
но аналогичные результаты,
доказываемые позже для контекстно-свободных грамматик,
используются во многих доказательствах и алгоритмах. Не все конечные
автоматы подходят для конструирования
распознающих устройств, пригодных для практических приложений,
так как в общем случае конечный автомат
не дает точного
указания, как поступать на очередном шаге,
а разрешает продолжать вычислительный процесс несколькими способами.
Этого недостатка нет у детерминированных конечных автоматов
(частного случая недетерминированных конечных автоматов),
определенных в разделе 2.6.
В разделе 2.7 доказывается, что
каждый автоматный язык
задается некоторым детерминированным конечным автоматом. Определение 2.1.1
. Конечный автомат
( finite automaton
, finite
-state machine) -
это пятерка ,
где -
конечный входной алфавит
(или просто алфавит
) данного конечного автомата, и - конечные множества, Пример 2.1.2
.
Пусть Q = {1,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}
, Определение 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
.
Рассмотрим конечный автомат 2.1. Недетерминированные конечные автоматы
,
то
называется переходом
(transition) из p
в q
,
а слово x
- меткой
(label) этого перехода.
, I = {1}
, F = {2}
,
-
конечный автомат.
,
то язык, распознаваемый конечным автоматом ,
содержит ., I = {1}
, F = {1,2}
,
является автоматным.,
где Q = {1,2,3,4}
, 
, I = {1,2,4}
, F = {1,3,4}
,
