DRAKON.SU

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

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

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

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

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

Как правильно изображать конечные автоматы на языке ДРАКОН?

Илья Ермаков считает, что так:
1. Берём силуэт.
2. Каждое из состояний соответствует ветке силуэта.
3. Названия веток - это названия состояний.
4. Веток, не соответствующим состояниям, в силуэте нет.

Идея хорошая, но есть проблема.
Пребывание автомата в каком-то состоянии - это ожидание сообщения извне.
(Ожидание "символа входного алфавита".)
Но икона "Название ветки" в языке ДРАКОН не означает задержки или ожидания!

По аналогии с межпроцессным взаимодействием, предлагаю использовать для
ожидания сообщений икону Ввод.
См. viewtopic.php?f=62&t=4275#p78554

Но тем не менее идея об изображении состояний при помощи веток хороша.
С учётом этого, автомат можно изобразить так:
1. Берём силуэт.
2. Каждое из состояний соответствует ветке силуэта.
3. Названия веток - это названия состояний.
4. В силуэте ЕСТЬ ветки, не соответствующие состояниям.
5. Первой иконой в ветках-состояниях является икона "Ввод".

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


И ещё одно дополнение.
Последняя ветка является особой. Она выполняется, когда автомат останавливают извне.

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

Последняя ветка - это деструктор.

Прилагаю пример автомата, который разбивает текстовую строку на слова.

Зачем изображать конечные автоматы при помощи ДРАКОНа?

ДРАКОН позволяет изобразить конечный автомат как единую сущность на одной визуальной сцене и при этом
показать алгоритм его работы. С ветвлениями и циклами!

Непрерывная логика работы автомата не разделяется на куски-колбэки,
а представляется в виде единого потока выполнения.

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

Похоже, что эта тема будет обобщающей.

Поэтому дам здесь ссылки на предыдущие обсуждения по Конечным автоматам:

1. Предложение по силуэту для разработки КА
Автор темы: MaximGB
viewtopic.php?f=78&t=4069

2. Дмитрий Владимирович Барановский сказал:
viewtopic.php?p=75873#p75873

Степан, полностью с Вами согласен - я так всегда и подразумевал разработку в автоматном стиле на ДРАКОНе.

Правильно ли я понимаю, что RECEIVE считывает 1 символ из output и работает с ним до следующего RECEIVE?
Т.е. в алгоритме существуют "проколы сути" от иконы "Параметры" до икон с RECEIVE?

Вообще тут хотелось бы контрпример - когда силуэт не является автоматом (и которым из: [не]детерминированным [не]конечным)?..

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

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

Я просто имел в виду, что силуэт без веточных циклов - просто примитив.
Но и примитив можно представить в виде автомата.

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

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

Что такое Math-Net.Ru


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

Привожу аннотацию к статье.

http://www.mathnet.ru/php/archive.phtml ... n_lang=rus



=======================
Уважаемые коллеги!

Многие участники нашего форума интересуются математикой. Пользуясь случаем, приглашаю Вас заглянуть на Общероссийский математический портал Math-Net.Ru и познакомиться с новой информацией о математической жизни в России.

Портал производит хорошее впечатление. Буду рад, если участники и гости форума заинтересуются этим Порталом и найдут для себя что-нибудь полезное.
http://www.mathnet.ru/

Заодно напоминаю, что с языком ДРАКОН связано очень много математических вопросов, и далеко не все из них исследованы и опубликованы.

Темы, касающиеся языка ДРАКОН, по-прежнему ждут своих пытливых исследователей.

В английской Википедии есть статья Algorithmic State Machine

В русской Википедии такой статьи нет.

Подготовка к встрече с Владимиром Ивановичем Шелеховым
из Института систем информатики имени А.П. Ершова
Сибирского отделения Российской академии наук


Есть иное предложение.

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

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

Насколько я помню Илья Евгеньевич Ермаков тоже поддерживает такое предложение.

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

Уважаемые коллеги!

Прошу критиковать (или поддержать, или уточнить, или видоизменить).

Ждать не надо, достаточно проверить состояние внешних сигналов, т.е. внешних, общих переменных.

Владимир Иванович Шелехов прислал письмо с ценными замечаниями и возражениями по данной теме:

Формально это правильный ответ. Парсер и лексер — типичные программы-функции.
На вход поступает последовательность символов. На выходе получается некая структура.

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

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



Конечные автоматы и по сей день занимаются разбором текста. Правда, обычно конечный автомат не проектируют непосредственно.
Вместо этого пишут программу, которая строит автомат. Пример — LALR-парсер.
http://en.wikipedia.org/wiki/LALR_parser_generator

Продолжаю атаку на позиции Владимира Ивановича Шелехова.


Это задача поиска первого слова для каждой строки текста.

Вполне понятная, читаемая программа. Она для каждой строки последовательно проходит через несколько стадий:
1. Пробелы в начале строки.
2. Первое слово.
3. Оставшаяся строка.

Выполняемые действия зависят от:
1. Типа символа: конец строки, пробел, прочие.
2. Стадии обработки строки.

То есть имеем скрытый, замаскированный конечный автомат.
Вот он в явном виде (на языке ДРАКОН-Javascript):


Что нагляднее — дело вкуса.


Не могу согласиться с этим утверждением. Оно слишком жёсткое.
Однако можно переписать его в более спокойном виде:

Прочитал с большим интересом.
За предикатным программированием — наше светное будущее. В отличие от функционального, оно действительно может стать декларативным.
Зачем это надо?
1. Чтобы автоматически доказывать правильность программ.
2. Чтобы автоматически документировать программы.
3. Чтобы автоматически программировать, чöрт побери. Пускай компьютер сам создаёт алгоритмы (ну хотя бы код-клей).

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

И ДРАКОН отлично сочетается со всем этим!
Вот моя попытка перевести текстовый вариант приведённого в статье автомата в ДРАКОН.