DRAKON.SU

Текущее время: Четверг, 28 Март, 2024 23:21

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 12 Март, 2013 18:13 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
Что такое конечный автомат?

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

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

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

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

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

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

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

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

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

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


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

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

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

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


Вложения:
Комментарий к файлу: Конечный автомат на языке ДРАКОН.
lex.png
lex.png [ 64.36 КБ | Просмотров: 25037 ]
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 12 Март, 2013 18:37 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
Зачем изображать конечные автоматы при помощи ДРАКОНа?

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 12 Март, 2013 18:41 
Аватара пользователя

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


Вложения:
Комментарий к файлу: Лексер на ДРАКОН-Си (конечный автомат).
lexer.png
lexer.png [ 101.69 КБ | Просмотров: 25034 ]
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 12 Март, 2013 20:30 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Похоже, что эта тема будет обобщающей.

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

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

2. Дмитрий Владимирович Барановский сказал:
Дмитрий_ВБ писал(а):
понятие "силуэт" шире понятия "автомат", но силуэт может выполнять и функцию автомата, если это будет нужно прогрммисту.
viewtopic.php?p=75873#p75873


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 12 Март, 2013 21:33 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Степан, полностью с Вами согласен - я так всегда и подразумевал разработку в автоматном стиле на ДРАКОНе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Среда, 13 Март, 2013 00:09 

Зарегистрирован: Понедельник, 09 Ноябрь, 2009 17:29
Сообщения: 904
Откуда: Россия, Питер
Степан Митькин писал(а):
А вот пример реального автомата на ДРАКОН-Си, который производит несложный лексический анализ.
Вместо иконы "Ввод" по бедности используется икона "Действие" с текстом "RECEIVE".

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 26 Март, 2013 14:36 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Вообще тут хотелось бы контрпример - когда силуэт не является автоматом (и которым из: [не]детерминированным [не]конечным)?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 26 Март, 2013 14:55 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 234
Откуда: Украина, Киев
Не автомат - нет циклов, не детерминированный - возможен переход на случайный адрес... как-то так


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Пятница, 29 Март, 2013 10:12 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Пятница, 29 Март, 2013 10:41 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 234
Откуда: Украина, Киев
Я просто имел в виду, что силуэт без веточных циклов - просто примитив.
Но и примитив можно представить в виде автомата.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Среда, 03 Апрель, 2013 18:25 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Ну да... вот и вопрос, а что же это за силуэты, непредставимые автоматно (наличие каковых и должно делать понятие "силуэт" шире понятия "автомат" как модель потока управления деятельности)... какими свойствами они обладают?..


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Среда, 30 Октябрь, 2013 17:01 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Сегодня я случайно обнаружил на сайте Math-Net.Ru свою старую математическую статью по теории автоматов, опубликованную свыше сорока лет назад.

Что такое Math-Net.Ru
Цитата:
Общероссийский математический портал http://www.mathnet.ru/

Общероссийский математический портал Math-Net.Ru — это современная информационная система, предоставляющая российским и зарубежным математикам различные возможности в поиске информации о математической жизни в России.


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

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

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

Цитата:
Пробл. передачи информ., 1972, том 8, выпуск 3, страницы 67–79 (Mi ppi855)

--------------------------------------------------------------------------------
Теория автоматов

PDF версия HTML версия

Анализ линейных фильтров Хаффмена при произвольных начальных условиях

В. Д. Паронджанов

Аннотация: Приводится математическое описание работы линейных фильтров Хаффмена при любых начальных условиях в неавтономном и автономном режимах. Излагаются методы решения неоднородных разностных уравнений над полем GF(2), вычисления последовательности на выходе любого разряда, нулевых последовательностей, а также кодовых колец типа A. Устанавливается зависимость периода автономной последовательности от делимости многочлена начального состояния и усеченного характеристического многочлена. Рассматриваются последовательное соединение и условия эквивалентности фильтров, фильтры общего вида, коррекция вектора состояния и т.д.

УДК: 621.391.172

Поступила в редакцию: 19.01.1971

Образец цитирования: В. Д. Паронджанов, “Анализ линейных фильтров Хаффмена при произвольных начальных условиях”, Пробл. передачи информ., 8:3 (1972), 67–79


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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Четверг, 04 Сентябрь, 2014 08:34 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
В английской Википедии есть статья Algorithmic State Machine

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

Цитата:
The Algorithmic State Machine (ASM) method is a method for designing finite state machines. It is used to represent diagrams of digital integrated circuits. The ASM diagram is like a state diagram but less formal and thus easier to understand. An ASM chart is a method of describing the sequential operations of a digital system.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Пятница, 07 Ноябрь, 2014 17:52 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Подготовка к встрече с Владимиром Ивановичем Шелеховым
из Института систем информатики имени А.П. Ершова
Сибирского отделения Российской академии наук


В сообщении viewtopic.php?p=78588#p78588 Степан Борисович Митькин писал(а):
...............................
Идея хорошая, но есть проблема.
Пребывание автомата в каком-то состоянии - это ожидание сообщения извне.
(Ожидание "символа входного алфавита".)
Но икона "Название ветки" в языке ДРАКОН не означает задержки или ожидания!

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

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

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

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

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Пятница, 07 Ноябрь, 2014 18:12 

Зарегистрирован: Воскресенье, 06 Апрель, 2008 14:43
Сообщения: 1657
Владимир Паронджанов писал(а):
В сообщении viewtopic.php?p=78588#p78588 Степан Борисович Митькин писал(а):
Идея хорошая, но есть проблема.
Пребывание автомата в каком-то состоянии - это ожидание сообщения извне.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Пятница, 07 Ноябрь, 2014 22:33 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Владимир Иванович Шелехов прислал письмо с ценными замечаниями и возражениями по данной теме:
Цитата:
Здравствуйте, Владимир Данилович!

После командировки я стану нормальным участником форума и буду отвечать там.

Есть два возражения.

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

Все ли программы являются реактивными системами?
Ответ -- нет.

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

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

Теперь вопрос -- являются ли сканеры и лексические анализаторы реактивными системами.
Ответ --- нет..

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

Правильное решение этой задачи я поместил в статье
http://persons.iis.nsk.su/files/persons ... tring1.pdf
в разделе 5 на стр.9

В подтверждение того, что лексические анализаторы программируются конечными автоматами, Шалыто ссылается на Ахо - Ульмана.
Но они не правы.
Так было лишь в 1970-ых, но не позже.
Я это знаю, потому что сам 30 лет занимался трансляторами.

Всего доброго.
С уважением,
Шелехов Владимир


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Понедельник, 29 Декабрь, 2014 21:06 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
Владимир Паронджанов писал(а):
Владимир Иванович Шелехов прислал письмо с ценными замечаниями и возражениями по данной теме:
Цитата:

Теперь вопрос -- являются ли сканеры и лексические анализаторы реактивными системами.
Ответ --- нет..

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

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

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

Владимир Паронджанов писал(а):
Владимир Иванович Шелехов писал(а):
В подтверждение того, что лексические анализаторы программируются конечными автоматами, Шалыто ссылается на Ахо - Ульмана.
Но они не правы.
Так было лишь в 1970-ых, но не позже.


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Вторник, 30 Декабрь, 2014 01:30 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
Продолжаю атаку на позиции Владимира Ивановича Шелехова.

Владимир Паронджанов писал(а):
Владимир Иванович Шелехов прислал письмо с ценными замечаниями и возражениями по данной теме:
Цитата:
Правильное решение этой задачи я поместил в статье
http://persons.iis.nsk.su/files/persons ... tring1.pdf
в разделе 5 на стр.9
Код:
FirstWords1(string in, string out* : ) {
   skipSpaces(in.cdr, in.car : in, char c);
   getWord(in, c, out : in, c, out);
   string out = out + '\n';
   skipLine(in, c : in, c);
   if (c != EOF) FirstWords1(in, out: out);
}


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

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

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

То есть имеем скрытый, замаскированный конечный автомат.
Вот он в явном виде (на языке ДРАКОН-Javascript):
Вложение:
LineScanner.png
LineScanner.png [ 48.23 КБ | Просмотров: 22594 ]


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

Владимир Иванович Шелехов писал(а):
Применение автоматного программирования для программ-функций противопоказано.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Четверг, 01 Январь, 2015 18:47 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Владимир Паронджанов писал(а):
Еще одна ссылка на работу Владимира Ивановича Шелехова
http://www.ssc.smr.ru/media/ipuss_conf/15/8_09.pdf

Цитата:
Язык и технология автоматного программирования для разработки систем управления


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: ДРАКОН и конечные автоматы
СообщениеДобавлено: Пятница, 02 Январь, 2015 00:35 
Аватара пользователя

Зарегистрирован: Вторник, 04 Октябрь, 2011 17:45
Сообщения: 585
Владимир Паронджанов писал(а):
Владимир Паронджанов писал(а):
Еще одна ссылка на работу Владимира Ивановича Шелехова
http://www.ssc.smr.ru/media/ipuss_conf/15/8_09.pdf

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

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

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


Вложения:
AAL-2.png
AAL-2.png [ 315.09 КБ | Просмотров: 22520 ]
Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB