Arduino.ru

Евгению:

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

Мне кажется, что в изложении теории автоматов нужно придерживаться чисто практического подхода: что это как  и зачем?

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

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

1. Описали в таблице нашу задачу;

2. "Причесали" таблицу по требованиям автомата;

3. начали писать программу:

3.1. описали события, все события - и таймеры и прерывания и кнопки и сообщения по каналам связи;

3.2. описали действия;

3.3. выписываем по очереди состояния с переходами.

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

----

вот, как-то так.

Может и так, Бог его знает.

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

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

А про теорию, так я не хотел в неё сильно погружаться, но хоть определения-то надо дать. А то тут на форуме появляются перлы типа "структура состояния" - какая может быть структура у атомарного объекта, хрен его знает, но обсуждается же на голубом глазу некоторыми "великим спецами во всём подряд".

И кстати, классический пример атомата - лексический анализатор. Можно сделать пример универсального парсера всего и вся, а то темы "как скорость из GPS выдрать" уже классикой жанра становятся.

Пайду в дальний скит, сыпать лысину пеплом. :( 

А Вы то здесь причём? За структуру, вроде, Великий вещал.

Мне очень стыдно, но такая штука есть. Это flex, бывший lex. ;) ;) ;).

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

----

Все выше - шутка, это, очевидно, тебе известно. Ты хочешь какое-то подмножество flex, которое можно реализовать на Ардуинке? Снова огорчу тем, что дебилам, которые задают вопрос о том, "как скорость из GPS вытащить?" придется учить язык регулярных выражений! А это вообще не реально! ;)

Я не "птица обломинго"! Я сам и лексические анализаторы писал и компилятор, пусть немноого наивные. Мы с тобой уже не молоды... нужно попробовать придумать то, что ДЕЙСТВИТЕЛЬНО будут использовать, а не то, что нам же докажет нашу невъебенную квалификацию.

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

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

Я это к чему? К тому, что человек (наш воображаемый пользователь), создавая автомат, не может сразу начать думать в коридоре возможного, нельзя сказать человеку: "памяти в автомате нет", он интуитивно этого не поймет и будет размышлять, что "вот-тут мы контекст запомним". Сорри, немного сумбурно.

И таким образом, давая человеку "тут - добавить и там прибавить", мы потеряем стройность языка описания автомата и придем снова к Я.В.У.

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

Не ясно, смогут ли концепцию автоматической генерации кода осилить? Будет 100500 вопросов: "а куда этот файл засунуть?" ;) ;) ;).

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

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

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

Еще вопрос: а что делать с кириллицей???? Поддерживаем Юникод или шлем в пень? всего два выхода. (я - за пень!)

Мужики. Евгений и Дракула! Понимаю. что возможно ломаю вам кайф - но на правах того, кто косвенно поднял  эту тему...

По-моему, вы куда-то не в ту степь идете. Мне. как продвинутому новичку, не кажется интересным создание автоматического генератора автомата на основе таблички из экселя. Кто-то из вас уже упомянул в связи с этим FLProg - по-моему. очень к месту. Подобный генератор скриптов, как и FLProg - это костыль для тех, кто не хочет погружаться в ЯВУ. Если же ты знаешь Си - написать реализацию автомата лучше и правильнее самому, нежели править автоматически сгенеренный скрипт, который никогда не будет таким же простым и понятным, как написанное хотя бы средним программистом.

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

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

Не, ну ещё есть чиновники, которым иногда надо отчитыватсься за внедрение инноваций. "Вот тут и начинается кино" как говаривал Ю. Визбор :) Я ж не зря написал

замечание в скобках ... маловероятно, но бывает :))))

Это как?

А где же он тогда свое собственное состояние запоминает? А таблицу переходов где?

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

конечно в ноосфере, а где ж еще?

Евгений, спасибо за терпение, почистил. Благодарность всем отозвавшимся (ссылки не потерялись).
Это как подписку оставьте, плиз.

Поскольку Женя не начинает я пока, так сказать, "на разогреве".

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

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

- Булеву алгебру;

- Логику предикатов, слово "квантор" вообще слышал ли?

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

- знаком ли с теоремой индукции, с принципом Дирихле?

- как ты понимаешь понятие "сложность вычисления"?

- собственно что слышал о теории алгоритмов?

- что есть "машина Тьюринга"? Что есть "тезис Черча"?

- разрешимость-неразрешимость, фактическая неразрешимость на примере двухключевого алгоритма?

==================

ой! шото меня понесло.... ;). Но, тем не менее, вот это примерный план того, что нужно ОБЯЗАТЕЛЬНО знать, чтобы рассуждать об автоматах на хоть сколько-то "не детсадовском" уровне. План не полный.

Есть желание слушать, в смысле - читать, подобные лекции? Ок. Выражай желавние явно, Евгений, верю, присоединится. Я бы хотел более широкой аудитории. Ну, то есть, хотя бы двое слушателей ;).

Дракула

1. Зовут меня Дмитрий, по возрасту - твой ровесник, образование высшее, но не математическое. Когда-то увлекался математикой. делал успехи, звали поступать в МВТУ - но не пошел. В дальнейшем с математикой пути разошлись, поэтому. чтобы не уподоблятся "знатокам 20 языков" - правильнее будет считать. что никакой математической базы у меня нет.

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

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

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

Вот тут пример, подходящий мне по уровню - тут мне все понятно, входы, выходы, таблица переходов...

http://www.ti.com/lit/ml/swrp161/swrp161.pdf

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

Там всё очень просто, люди просто пытаются объяснить строго, с упором на определения, вот и получается хренова гора греческих букв.

Если на пальцах, то

Автомат Мили: выходы (действия, типа "запустить мотор") выполняются в момент перехода между состояниями. Т.е. какое именно действие выполнится зависит от исходного состояния и входного символа. А когда автомат уже попал в новое состояние, то в нём он просто сидит и ждёт новых входных символов.

Автомат Мура: выходы выполняются когда автомат попадает в некоторое состояние (независимо от того, как и откуда он туда попал). Т.е. какое именно действие выполнится, определяется только состоянием.

Поэтому отличить один от другого - нет ничего проще. Если таблица описывается в терминах "если в состоянии Х прилетел входной символ Y, то выполнить действие Z и перейти в состояние S" - автомат Мили - действия на переходе. А если "если в состоянии Х прилетел входной символ Y, то перейти в состояние S", а при описании состояний добавляется "попав сюда надо выполнить действие Z" - автомат Мура.

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

Вот собственно и весь автомат, если я нигде не лопухнулся по спешке (на пересечении состояний и входных символов сверху пишется выход (что сделать), а снизу – состояние, в которое перейти, null – ничего не делать):

Его можно ещё упростить при условии, что допустимо включать уже включённое освещение и выключать уже выключенное. Тогда, вместо состояний S2 и S3, можно было бы записать одно, а заодно и выходы O1 c O3 объединить.

Обратите внимание, что на пересечении S1-I2 и S3-I4 целевое состояние одно и тоже, но выходы (действия) разные. Тоже самое на пересечениях S2-I2 и S3-I1, а также S2-I3 и S3-I3. В автомате Мура, где выход (действие) определяется только состоянием, такие шутки невозможно. Там пришлось бы заводить больше состояний или как-то ещё решать эту проблему.

Только здесь имеется путаница (небрежность) в терминологии (характерная даже для академических журналов). Вообще-то классический конечный автомат не выполняет никаких действия (правильные слова: "не имеет выходного алфавита") от слова вообще. Он только переходит из состояния в состояние по воздействием входных символов. И результатом его работы является конечное состояние. Автомат, имеющий выходной алфавит (умеющий выполнять какие-то действия) - называется "конечный автомат с выходом". Так вот автоматы Мили и Мура - очевидно автоматы с выходом. Но в литературе очень часто опускают это слово и называют "конечные автоматы с выходом" просто "конечными автоматами", хотя строго говоря это неверно. Просто авторы считают, что из контекста понятно о чём речь и не перегружают текст постоянными упоминаниями о выходе.

...незаметно втянул брюхо и важно прохаживатся!....

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

Нет. А как мы из этого промежуточного состояния попадём в то, в которое изначально хотели? Если мы перейдём в промежуточное состояние, то мы в нём и остнемся и будем ждать новых входных символов. Даже если мы "через зад" решим эту проблему, например, фиктивным входным символом (специально для этого введённым), всё равно получится, что мы попали в целевое состояние "за два тика метронома", а не за один, как это было бы в автомате Мили.

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

ну да, понял - переход от Мили к Муру сложнее. Я. конечно, читая вас - подсматриваю в разные статейки в инете. Пользуясь подсказками, преобразовал ваш автомат управления освецениием из #17 из автомата Мили в Мура - получилось 6 состояний и 12 переходов, правильно? Картинку красивую вряд ли нарисую...

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

Проще всего представить так: Мур == состояние прибора, не в смысле автомата, а в смысле полезности: что-то включено, что-то работает, что-то греет или холодит, есть результат измерений и переключений всякого управляющего мусора. ;)

Мили == полезное действие прибора есть результат воздействия управляющего (или измеряемого) фактора.

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

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

Это не особенности модели, а особенности человеческого мышления.

Но полезно, сперва, вообще осознать понятие вычислительной модели. Понять их общие классы по эквивалентности. Понять, как устроены доказательства теорем эквивалентности, чтобы не возникало вопросов: "как переделать автомат Мура в Мили и наоборот?". Там все изоморфизмы строятся очевидно, и на интуитивном уровне. Но "от букваря" почему-то никто идти не хочет!

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

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

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

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

Автомат Мили, автомат Мура. Ладно пусть будет автомат Пуха, если в каноны не вписывается. В общем заводится внутреняя функция void stand(state_t s); Вот она и перещелкивает автомат в нужное состояние и запускает выполнение действия на этом состоянии. Можно и наоборот сначало действие, потом перевод в нужное состояние . Но все это в одной функции. Иначе это не "мой" автомат и никаких притензий на работу "чужих" автоматов я не несу.

У мня на автоматах Пуха какрас бочка в теплице и живёт, не зная про Муров и Милей. 

Коллеги, примите меня в читатели... Уровень мой наверно сами видите. Это уровень b707 поделить на 10. Есть желание разобраться во многих вопросах.  Моё почтение за уроки.

b707,

Вы так не напрягайтесь. Влад прав, но это его правда, а не наша. Поймите, он логик - для него автомат это пятёрка:

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

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

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

P.S. Мне коллеги прислали реализацию на массиве списков в виде библиотеки для Ардуино, но там нет службы времени. Я добавлю её и тогда выложу с примерами (начну с примера, что мы выше разбирали). Но, боюсь, что не раньше субботы, тут столько всего навалилось.

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

Когда учился я, дело обстояло в точности таким же образом. Точнее - мне читали численные методы, а ни теории алгоритмов, ни даже того, что существет такая дисциплина, я не знал.

Но - при этом, после окончания ВУЗ'а, решал конкретные задачи. Для их решения использовал как знания, полученные в ВУЗ'е, так и то, что изобрел самостоятельно. В до-Интернетную эпоху это было вполне естественно. Среди моих изобретений было и то, что сейчас принято называть конечными автоматами (точнее, как я только что узнал, - конечными автоматами с выходом).

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

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

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

PS. Да, уверен, что кроме перечисленных существуют и другие типы автоматов. Я, например, иногда применяю автоматы, которые обладают не одним, а двумя или тремя состояниями. Конечно, они точно так же сводимы к автоматам с единственным состоянием, но тут просто вопрос удобства (как для теоретика выбор между Мура и Мили). Думаю, что такие автоматы для людей, занимающихся теорией автоматов, тоже имеют какие-нибудь особенные названия.

Подтверждаю.  Мне в матфизике читали только численные методы и никаких алгоритмов.  Язык Фортран.  До сих пор помню курсовик по вычислению функций Струве (простой и модифицированной).  С графиками :) 

Женя прав абсолютно!  Есть типовые приемы построения изоморфизмов в разных вычислительных моделях. Где-то произведения множеств, где-то экспонента (в Теории Множеств это переход к множеству всех подмножеств), где-то построение диагонали (из первого первый, из второго - второй...). Это типовые приемы, которые математику "вбиты" до корней зубов.

Есть реальные проблемы: доказательства финитности, конструктивные доказательства финитности, эффективно высичлимые доказательства финитности, полиномиальные доказательства финитности.... ;) - конечно, я нарочно написал, чтобы смешно выглядело, но ЭТО и есть основные проблеммы теории алгоритмов. Финитность и эквивалентность.

А так, надеюсь читатель с легкостью докажет, что любой комп на его столе - конечный автомат. А как иначе? Входной алфавит - на лицо: все кнопки  + биты по линиям связи. Состояния - память ОЗУ+диски или ссд. Даже учет облака не меняет, по большому счету, ничего, ведь объем всех дисков всех облаков  все равно конечен. Число возможных состояний это экспонента от объема памяти, пояснять надо?

НО, еще раз большими и жирными: НО!!! Число частиц, в обозримой вселенной, примерно 3.3E80,  это порядка 2**241. То есть число состояний, как конечного автомата, даже у тиньки13 - уже во много-много-много раз больше, чем элементарных частиц во вселенной. Следовательно это хоть и конечный автомат - формально, но эффективно - нет. За разумное время мы не сможеи успеть применить теорию КА даже к тиньке13.

Например формально у КА не стоит проблема отановки, или финитности алгоритма. В реальности мы не сможем определить финитность даже в коде новичка для тиньки!

----

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

я наверно забегаю вперед - но можно вопрос?

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

Цепочка переходов между стадиями такая:

А - В - А - С -А

как видим, после А следует то B. то С

Вопрос - если у КА "нет памяти", каким образом можно определить, куда следует переходит из состояния А - в В или в С ? Или это вообще неправильное описание автомата?

Пока из чтения теории я вижу только один "правильный" выход - считать состояния "А перед В" и "А перед С" - разными, тогда граф получается

Ав - В -Ас - С -Ав -... и всякая неопределенность пропадает.

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

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

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

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

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

Тогда для такого "автомата" массив нужен с директивами куда прыгнуть на текущей стадии. Roadmap, так скыть.

я извиняюсь, но почему именно "прав ДетСимен" ? :) - я эту идею в своем вопросе озвучил раньше! :) обидно... :)

Ок, вопрос такой - использование переменной для хранения контекста - это совсем не вписывается в теорию или такой метод допустим?

Филин, ты тоже прав, и даже прав первее меня.  Ниабижайся. :) 

Я всё про бочку свою.  :)  

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

Как это по теории разбить на несколько пред/пост состояний, я даже не догадываюсь. :) 

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

Добрый день!

С ардуино знаком плохо, но очень нужно реализовать следеющее:

Есть кнопка и диод.

При замыкании кнопки, диод включается на 4 секунды и выключается. Цикл остановился, кнопка замкнута, диод не горит. Ждем размыкания кнопки.

При размыкании кнопки происходит тоже самое- диод включается на 4 секунды и отключается. Цикл остановился, кнопка разомкнута, диод не горит. Ждем замыкания кнопки.

=================================

Строим автомат Мили, т.е. действия на переходах. Сперва определим состояния автомата, затем входные события, затем построим предварительную таблицу действий и переходов.

Есть "подводные камни". ;) Я про них потом напишу. Хорошо, если читатели заметят. Антидребезг пока игнорируем.

Поехали!

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

И Влад, уточни - автомат будешь расписывать ты или это задание для участников?

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

До кода доводить не станем, останемся на уровне метакода.

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

состояния два - "диод горит" и "диод не горит"

входных сигнала тоже два - "состояние кнопки изменилось" и "истек таймаут 4 сек"

таблицу переходов как красиво отобразить, не знаю, если словами. то так:

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

Вроде все

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

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

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

Итак у нас два компонента системы - диод и кнопка. Каждый может быть в двух состояниях, произведение этих множеств и есть множество состояний системы:

00 - кнопки и диод выключены;

01 - кнопка отпущена, диод горит;

10 - кнопка нажата, диод выключен;

11 - кнопка и диод включены.

------------------------

события:

K1 - нажатие кнопки;

K0 - отпускание кнопки;

T - истечение таймера;

----------------------

действия:

D0 - выключить диод;

D1 - включить диод;

T1 - запустить(или перезапустить) таймер на 4 сек;

T0 - выключить таймер.

-----------------------------------------------

Переходы:

(добавлю про выбранный синтаксис: слева {состояние, событие}, справа {состояние,(действия,...)} )

{00, К1}:{11,(D1,T1)};

{11, К0}:{00,(D0,T0)};

{11, T  }:{10,(D0,T0)};

{10, К0}:{01,(D1,T1)};

{01, К1}:{11,(D1,T1)};

{01, T  }:{00,(D0,T0)};

====

остается 6 пар состояние + событие, которые не рассмотрены, перечислим и прокомментируем:

00, K0 - не может быть отпущена отпущенная кнопка - ошибка кнопки;

00, T   - не может работать таймер при погашенном диоде - ошибка таймера;

11, K1 - не может быть нажата нажатая кнопка, ошибка кнопки;

01, K0 - не может быть отпущена отпущенная кнопка - ошибка кнопки;

10, K1 - не может быть нажата нажатая кнопка, ошибка кнопки;

10,  t   - не может работать таймер при погашенном диоде - ошибка таймера;

====

то есть наш автомат еще и немножко сам себя диагностирует.

---------------------------------------------------------

Поскольку в первом примере все написал сам, то пусть кто-нибудь закодирует это. Мне это нужно для комментирования особенностей реализации автоматов на Ардуино.

Хрена себя у вас тут дела пока я на совещании зеваю

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

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

void automata_step() 
{
	select (cur_state) {
		case (00)
		  if (K1) {
                      diode_ON();
		      set_timer(4sec);
                      set_state(11);
                    }
                  break;

		case (11)
		  if (K0) {
                      diode_OFF();
		      timer_off();
                      set_state(00);
                    }
		  if (timeout()) {
		      diode_OFF();
		      timer_off();
		      set_state(10);
                  break;

		case (10)
		  if (K0) {
                      diode_ON();
		      set_timer(4sec);
                      set_state(01);
                    }
                  break;

		case (01)
		  if (K1) {
                      diode_ON();
		      set_timer(4sec);
                      set_state(11);
                    }
		  if (timeout()) {
		      diode_OFF();
		      timer_off();
		      set_state(00);
                  break;
  }
}

вроде не напутал

сорри ха форматирование - когда открываю сообщение чтобы поправить - в редакторе все отступы ровные, так что как править не понятно

Замечание не по сути программы а по структуре и оформлению.

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

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

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

typedef bool(* TSignalFunction)(void);
typedef void(* TResponseFunction)(void);

//
//	Ячейка таблицы
//
struct SSolution {
	TSignalFunction Signal;	// адрес функции входа
	TResponseFunction Response;	// адрес функции выхода
	const unsigned	NewState;	// новое состояние
	const SSolution * Next;	// адрес следующего элемента или NULL, если последний
};

Давайте попробуем записать входы, выходы и таблицу для того автомата, что я приводил в посте №17

Для начала пишем входы и выходы. Они достаточно тривиальны

//
// Конфигурация пинов
//
static const int8_t pin_photoSensor = A1;
static const int8_t pin_motionSensor = 5;
static const int8_t pin_lampRelay = 6;

//
//	Входы автомата
//
static inline bool svetlo(void) { return analogRead(pin_photoSensor) > 400; }
static inline bool temno(void) { return analogRead(pin_photoSensor) < 300; }
static inline bool motionDetected(void) { return digitalRead(pin_motionSensor); }
static inlone bool timerElapsed(void) { return TheTimer.elapsed(); }
//
//	Выходы автомата
//
static inline void initTimer(void) { TheTimer.init(); }
static inline void lightOFF(void) { digitalWrite(pin_lampRelay, LOW); }
static inline void initTimerAndLightOn(void) { initTimer(); digitalWrite(pin_lampRelay, HIGH); }

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

///////////////////////////////////////////////
//
//	Состояния автомата
//
enum  AUTOMATA_STATE {
	MODE_DAY = 0,
	MODE_NIGHT,
	MODE_NIGHT_LIGHT_ON
};

//
// первая строка таблицы
//
static const SSolution s10 = { temno, NULL, MODE_NIGHT, NULL };
//
// вторая строка таблицы
//
static const SSolution s21 = { motionDetected, initTimerAndLightOn, MODE_NIGHT_LIGHT_ON, NULL };
static const SSolution s20 = { svetlo, NULL, MODE_DAY, & s21 };
//
// третья строка таблицы
//
static const SSolution s31 = { motionDetected, initTimer, MODE_NIGHT_LIGHT_ON, NULL };
static const SSolution s30 = { svetlo, lightOFF, MODE_DAY, & s31 };
//
//	Массив строк таблицы
//
const SSolution * automataDefinition[] = { &s10, &s20, &s30 };

Вот собственно и всё. 

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

static unsigned machineState = 0;

unsigned mealyMachine(const SSolution ** definition) {
	SSolution * sol = (SSolution *) * (definition + machineState);
	while (sol) {
		if (sol->Signal()) {
			if (sol->Response) sol->Response();
			machineState = sol->NewState;
			break;
		}
		sol = (SSolution *) sol->Next;
	}
	return machineState;
}

Эта функция не меняется никогда, а чего её меняться-то?

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

Поная библиотека (со всеми нюансами) и полные работающие примеры будут в выходной (надеюсь).

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

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

Это не вписывается в формальную теорию КА, в некотором смысле это суперпозиция КА, но программировать без этого "усовершенствования" невозможно.

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

---------------

Я ушел на паузу до завтра. Возможно загляну вечером, но трезвости суждений не обещаю ;). Самогон сам себя не выпьет и сериалы сами себя не посмотрят! (для "танкистов" это аллюзия к сериалу Др.Хаус, о том,  что "порнуха сама себя из интернета не скачает!"). Всем - удачи.

----------------------

пока писал появился Евгений. Сорри.

А почему Вы решили, что "А в превой позиции" и "А в третьей позиции" - это одно и то же состояние?

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

А - А - А - А -А

Ну да. Именно это я и называл выше автоматом с двумя состояниями (одно состояние: A, B, C; другое: с, в).

Но как это по науке называется, не знаю.

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