Комментарии 26
не рассмотрены такие типы как:
- Вероятностный автомат
- Квантовый автомат
- Машина вероятности (Различные варианты понятия «Машины вероятности» являются обобщениями понятий «автомата детерминированного», «Тьюринга машина», «автомата бесконечного».)
не рассмотрено разделение по следующим типам:
- автоматы-распознаватели
- автоматы-преобразователи
- автоматы-генераторы
Вся статья в одном абзаце:
В ряде случаев в формировании выходного сигнала может задействоваться не только ячейка памяти, но и входной сигнал. Это позволяет сократить количество необходимых состояний. Такая схема называется автомат Мили.
Остальное - вода.
Количество "воды" в тексте скорее всего определяется Вашим уровнем погружения в проблематику, для Вас это все и так понятно и не имеет важного значения.
Я упоминал о проблемах "жонглирования" терминологией, это часто встречается в публицистических материалах, где авторы придерживаются аналогичной точки зрения. Это вызывает достаточно проблем у тех, кто начинает разбираться в материале самостоятельно.
Я просматривал большое количество статей по программированию ардуино. Там часто встречаются разные интерпретации терминов конечных автоматов. К примеру, встречаются абревиатуры FSM в названиях функций. И часто ни каких пояснений на этот счет не дается.
А связь между автоматом Мура и машиной Тьюринга? Это тоже кажется очевидным только для человека, который уже какое-то время связан с темой.
Я не оправдываюсь. Цель статьи была в том, чтобы сфокусировать внимание на базовых терминах и их связи друг с другом. И то, что Вы считаете "водой", является необходимой текстовой оберткой для этих терминов, чтобы сформировать определенное отношение к информации у читателя.
По ходу сами немного запутали тему. На рисунке про SFC показали Ladder диаграмму.
А Ladder диаграммы не демонстрируют состояний, это не есть изображение автоматов.
Сами SFC тоже только узкое подмножество реализаций автоматов.
Чистые автоматы Мура также не очень-то годятся для программирования из-за своей выразительной ограниченности и плохой масштабируемости.
На западе икона автоматного программирования - Miro Samek
Он сразу смекнул, что просто автоматных диаграмм недостаточно для облегчения программирования и сразу начал с UML и фреймворка под автоматы. Теперь там целая экосистема с тулсами, генераторами кода, отладчиками и проч.
Но это как бы бюджетный вариант.
Серьёзный вариант - это автоматные среды в Matlab (StateFlow) или LabVIEW (Statechart Module). И там будут не голые автоматы Мура, а комплексные проприетарные графические объекты, лишь частично подражающие автоматам, но они при этом гораздо выразительнее и читабельнее.
Спасибо за ссылки!
"Теперь там целая экосистема с тулсами, генераторами кода, отладчиками и проч. " посмотрел обучающее видео, где предлагается помигать светодиодом, выглядит настолько страшно, что новичкам точно не зайдет... удивительно, но примеры выглядят сложнее, чем могли бы быть (имхо)
Тексты автоматных программ не принято смотреть. Они синтезируются компиляторами из графической нотации. Вот графическую нотацию и представляют на обозрение.
Сам я с quantum leaps давно дел не имею. Их графическая нотация и возможности по кодогенерации и отладке слишком ограничены. Но там хорошо показана внутренняя кухня. Это хорошая альтернативна сбивчивым и путанным статьям по автоматному программированию.
Кстати да, отбивает охоту напрямую писать тексты в автоматном стиле. Этот метод давно устарел.
а как корректно реализовать работу с периферией: SPI, I2C, UART, АЦП, протоколы верхнего уровня? если нужных протоколов нет в базе или нужно самому описать (например, сохранение данных в ПЗУ? проприетарный протокол). Если нужно ногой подергать или данные вывода получить, или на экран вывести и библиотеки все есть, то понятно, а если библиотек под нужный процессор нет?
ps: ещё такой момент, кто отвечает за сброс автомата, чтобы он не завис в каком-то состоянии?
Вы как будто задаете вопрос в парадигме автора, который считает что теория автоматов как-то помогает в программировании. Это все равно что теория матриц помогала бы в схемотехнике. Однако математики не сильны в схемотехнике.
Я же считаю что автоматное программирование это прежде всего графическая нотация с явно изображенными состояниями. И главное преимущество в том что такая нотация избавляет от бесчисленных именований и облегчает глобальный рефакторинг алгоритмов и систем.
Но у этой нотации есть свои накладные. В частности при работе с периферией нужна постоянная работа и исследования на уровне символьной отладки и манипуляции с битами на уровне машинных кодов. Здесь сорсы сгенерированные из диаграмм состояний неудобны и процесс неоправданно затягивается..
Поэтому я не применяю метод диаграмм состояний для разработки драйверов. Автоматное программирование хорошо ложиться на сложные многосоставные системы где рефакторить приходится уже на уровне архитектуры приложения верхнего уровня.
Также не применяю автоматы для создания библиотек. Поскольку библиотеки обязаны иметь API. А реализовывать API в диаграммах состояний в графической нотации это удовольствие крайне сомнительное.
Чтобы автомат не зависал в него вставляют автоматы реализующие таймауты.
Как то у меня эта статья ассоциируется со школьной программой по информатике 30 летней давности. Когда классе в 7м начинается изучение двоичной системы исчисления, но до 11 класса остается совершенно непонятным зачем эта двоичная система исчисления была нужна и как она вообще связана с информатикой.
Это происходит потому, что в школьной программе был совершенно упущен пласт информации который позволял бы понять что вообще такое компьютер.
И из 2й системы исчисления школьники прыгали сразу в паскаль, где двоичная система нужна была разве чтобы сложные конструкции с if писать.
Так и в статье перечисляется набор фактов о развитии информатики и конечных автоматов, перечислены основные элементы, но вот как это работает непонятно.
Вроде как можно разобраться что простейший дверной замок это некий конечный детерминированный автомат Мура. (Есть два состояния. Некий сигнал-ключ может менять состояния.) А если замок устроен так, что правильный ключ нужен для того чтобы открытую дверь еще и распахнуть, то это уже ближе к автомату Мили.
А дальше разрозненные факты про машину Тьюринга и отсылка к тому что это разновидность автомата. И далее высокоуровневые автоматные языки программирования.
На самом деле любой компьютер это конечный автомат с колоссальным количеством состояний и алгоритмами перехода между состояниями зашитыми в процессор. ( Состояние это прям все отдельные биты любой памяти компьютера включая регистры). А ключом к пониманию автоматов является как раз осознание полноты и избыточности системы алгоритмов перехода между состояниями, адресации, разделения памяти на команды и данные и многое что еще.
Сами переходы между состояниями в любом компьютере осуществляются с использованием машинных кодов, которые, с момента включения питания компьютера выстраиваются в непрерывную цепь команд приводящих к изменениям состояний и в конечном итоге складываются в последовательность бит на экране компьютера подсвечивающих пиксели разных цветов.
Зачем нужно разбираться в классификации конечных автоматов, если только вы не разрабатываете свой процессор? В общем как и в любой огромной теме любое обсуждение рождает больше вопросов чем дает ответов и нужно множество примеров.
У меня не было цели разбираться в классификации. Посмотрите вебинар от яндекса, ссылка в начале есть. В терминах путаница полнейшая. А потом получается, что что-то полезное в теории фиг найдешь. В сети встречал доклад от программиста с яндекса, он рассказывал как использовать библиотеку автоматов для мобильных игр под IOS для приложений. И еще куча подобного есть.
Я прекратил слушать указанный вебинар Яндекс уже на первых минутах, когда лекторы не смогли внятно определить то о чем они собираются рассказывать. Стало ясно что их описание будет основано на процессе классификации банковских карт. (Что пожалуй не самое характерное применение). Мне кажется, что вы начали с очень верных вещей а именно связи формальной логики, математики, устройства памяти, а затем замяли основную канву и очень поверхностно описали задачи которые решают машины состояний и процесс их работы. Хотя базу подготовили прям очень хорошую.
За последнее время мне на доработку попадает уже второй проект на микроконтроллере. В последнем программа написана в около автоматном стиле. Вроде человек старательно писал. Но такого нагородил, что в конце уже как-то внятно дополнить функциональность невозможно. Программированием микроконтроллеров часто занимаются электронщики, которые программирование самостоятельно доучивали. Из-за недостатка теоретической базы такой трешак накручивают в программах.
Ну, кмк этому в институтах не учат. Скорее просто общей философии программирования. Хотя, довольно давно сталкивался с описанием "C" функции int atoi(char**) в разрезе машины состояний и это было пожалуй очень вдохновляюще. Весь бардак из вложенных условий и циклов рассыпался на переходы между состояниями и это позволило автору описать сложный механизм очень просто. Даже самому тогда захотелось попробовать написать реализацию. Жаль только статья потерялась за давностью лет. Признаться и сегодня хотел увидеть нечто подобное.
угу (вздыхая), а потом когда берешь в руки клавиатуру, все кажется автоматами с конечным (но это не точно) количеством состояний... знаем... проходили...
и кодишь автомат... просто потому, что так надежнее...
кто как в итоге кодит микроконтроллеры?
Автоматы стоит разобрать, чтобы, к примеру, документировать код. Диаграмм Мили - удобный инструмент.
Я имя типа и имя перечисления делаю одинаковыми, подчеркиваеие можно не ставить. В конце перечисления ставлю имя типа максимальное_состояние. С его помощью можно размеры массивов определять и прочее подобное.
Упомянутый выше " экосистема с тулсами, генераторами кода, отладчиками и проч. " очень помогает разработать архитектуру решения для микроконтроллера. Это вариант реализации концепции Visual Thinking с разными причудами. Тот же microsoft предлагает использовать FSM для написания UI под частные решения с микроконтроллерами. Я это использовал для проекта с stm32f4. С определенными ограничениями мне это понравилось.
А вообще, когда надо делать что-то серьезное с "0", то проект стоит начинать дизайнить в чем-то большом и развитом. Я люблю Sybase Power Designer. Только вот с FSM в нём трудно.
Как корабль назовёшь, так он и поплывёт: "С чем едят конечный автомат". В статье рассмотрели "конечный автомат" и даже их сорта не давая определения конечного автомата. Пичалька. Википедия на порядок информативней. https://ru.wikipedia.org/wiki/Конечный_автомат
Абстрактный автомат — это математическая абстрактная модель дискретного устройства, имеющего один вход и один выход, в каждый момент находится в одном состоянии из множества вовозможных.т
Определение в статье есть.
Хорошая цитата от туда -
Кроме того, попытка разработки сложной модели, реализованной конечным детерминированным автоматом, приводит к быстрому росту числа состояний автомата, что в итоге делает разработку такой модели крайне трудоёмкой. Как было отмечено выше, последнюю проблему можно решить, если использовать недетерминированный автомат.
Я бы добавил , что проблему решают иерархические автоматы и параллельные автоматы с механизмами событий.
Но это уже будут совершенно не автоматы Мура, а диаграммы состояний.
Вот тут главная путаница и состоит. Большинство за автоматы принимает или выдаёт обработчики иерархических состояний. Поскольку в чистых автоматах Мура программировать практически невозможно.
С чем едят конечный автомат