OberonCore
https://forum.oberoncore.ru/

Синтаксис конечного автомата в PureBuilder
https://forum.oberoncore.ru/viewtopic.php?f=93&t=3284
Страница 2 из 2

Автор:  Сергей Прохоренко [ Вторник, 01 Март, 2011 16:39 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Драконограф писал(а):
В свете сказанного в новой работе Шалыто и Поликарповой я бы несколько поменял оценки :| Именно изложение там ЯВС-метода меня, "предметника", навело на мысль о естественности представления автомата циклом Дейкстры ...


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

Драконограф писал(а):

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


Компилятор укажет на ошибки в таблице переходов в сопоставлении с массивом/строкой входных условий/символов. А как исправлять ошибки - решать программисту.

Автор:  Владислав Жаринов [ Среда, 02 Март, 2011 09:35 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

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

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

Автор:  Сергей Прохоренко [ Среда, 02 Март, 2011 10:12 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Драконограф писал(а):
Вопрос в том, чтобы уже в допрограммное представление вводить "алгоритмические разрешители" - чтобы трансляция всегда шла автоматически... и это (что вводится - как у Поликарпова и Шалыто или что-то иное? какими командами?) д.б. частью стандарта на представление автомата в структурном редакторе.


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

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

Автор:  Владислав Жаринов [ Среда, 02 Март, 2011 10:57 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

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

Сергей Прохоренко писал(а):
Я предложил ввести в PureBuilder конечный автомат, то есть, автомат, имеющий только входную ленту. Вы идете дальше, и предлагаете автомат с двумя лентами - входной и выходной. Я тоже думал об этом, но решил отложить это как-нибудь на потом. Мотивация следующая. Конечный автомат необходим для создания управляющих алгоритмов, поэтому это приоритет номер один. Автомат с двумя лентами имеет гораздо более узкое применение - в основном при разработке трансляторов языков программирования и, может быть, естественных языков.
...
Как Вы понимаете назначение выходной ленты в соотнесении МТ с КА (учитывая сказанное в п/р 1.3,1.4 той же выдержки, в т.ч. и о реализации управления объектами окружения)? Кстати, там же на с.10 упоминается выходная лента - но управление объектами далее никак не связывается с её наличием - всё представляется через одноленточные МТ... и я имею в виду именно учёт свойств множества переходов, описанных на с.77 (как будем в редакторе описывать противоречивые и/или неполные системы переходов и какие сочинителю дадим средства приведения к непротиворечивым и полным?), а не организацию МТ...

Автор:  Илья Ермаков [ Среда, 02 Март, 2011 12:08 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

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


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

Автор:  Владислав Жаринов [ Среда, 02 Март, 2011 13:56 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

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

Автор:  Сергей Прохоренко [ Среда, 02 Март, 2011 22:24 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Драконограф писал(а):
как будем в редакторе описывать противоречивые и/или неполные системы переходов и какие сочинителю дадим средства приведения к непротиворечивым и полным?


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

Автор:  Сергей Прохоренко [ Среда, 02 Март, 2011 23:15 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

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


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

См. http://www.swsys.ru/index.php?page=article&id=441 :
Цитата:
в сложных технологических установках число состояний автомата в рабочем цикле может достигать нескольких сотен

Автор:  Илья Ермаков [ Четверг, 03 Март, 2011 00:06 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Разработка сложной системы без декомпозиции как раз невозможна. Это - тупик, просто очень быстро достигается предел сложности.

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

Автор:  Сергей Прохоренко [ Четверг, 03 Март, 2011 00:22 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Илья Ермаков писал(а):
Разработка сложной системы без декомпозиции как раз невозможна. Это - тупик, просто очень быстро достигается предел сложности.

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


Здесь нет никакой сложности. Это очень гомогенная модель, можно сказать, линейная комбинация. От того, что мы расставим скобочки она не станет проще:

Код:
 (a1*x1 + a2*x2) + (a3*x3 + a4*x4) + (a5*x5 + a6*x6)


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

Автор:  Владислав Жаринов [ Четверг, 03 Март, 2011 05:13 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Сергей Прохоренко писал(а):
...
Я бы не стал разбивать автомат на несколько только ради того, чтобы облегчить жизнь программисту, так как модель может перестать правильно отображать действительность, а модификация ее может стать невозможной.
...
Да, декомпозиция должна быть сколь возможно естественной - можно идти от агрегации сложного реального объекта, например. И примеры этому Поликарпова и Шалыто тоже дают.

Автор:  Владислав Жаринов [ Четверг, 03 Март, 2011 13:11 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Сергей Прохоренко писал(а):
Драконограф писал(а):
как будем в редакторе описывать противоречивые и/или неполные системы переходов и какие сочинителю дадим средства приведения к непротиворечивым и полным?


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

Автор:  Илья Ермаков [ Четверг, 03 Март, 2011 16:21 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

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


Почему произвольную?
Не верю в то, что у системы из более чем десятка состояний нет "естественной структуры".
Скорее, нет привычки эту структуру усматривать и явно формулировать.

Автор:  Рыжий [ Четверг, 03 Март, 2011 18:10 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

В J есть конечный автомат, там для этого даже есть глагол специальный. Не помню только есть ли там бесконечный автомат.

Автор:  Сергей Прохоренко [ Четверг, 03 Март, 2011 22:31 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Драконограф писал(а):
структурный редактор будет проверять таблицы (диаграммы), принадлежащие каждой автоматной модели, на программируемость и вот этими "расцветками" указывать, где осталась противоречивость и/или неполнота?


Ага.

Автор:  Сергей Прохоренко [ Четверг, 03 Март, 2011 22:42 ]
Заголовок сообщения:  Re: Синтаксис конечного автомата в PureBuilder

Рыжий писал(а):
В J есть конечный автомат, там для этого даже есть глагол специальный. Не помню только есть ли там бесконечный автомат.


Это не ключевое слово, а два знака препинания:
Код:
 ;:

Страница 2 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/