Вышел FSME-0.9

a che eto takoe ?

Finite State Machine Editor

Редактор конечных машин состояний

http://fsme.sf.net

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

Представил: "Появился tutorial из 3 шагов, в котором жираф и бегемот помещаются в холодильник с помощью автомата" (Калашникова).

Страшная, антигуманная вешь этот ваш FSME-0.9 ;)

Народ, тут я недавно постил новость про fsme-0.8, и она не собиралась на gcc 3.2 никто не может проверить, почему?

Там всё очень просто - в 3.3 все STL SGI extensions перенесли из std в __gnu_cxx, и у меня на эту тему стоит дефин. Когда были 2 транслятора - 3.2 и 3.3 я проверил - оно работало (на debian). А на альтах не собиралось.

У кого альт и gcc-3.2 попробуйте транслянуться...

Мой :-)

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

Не собирается под debian/sid.

make[1]: Entering directory `/home/jk/tmp/fsme/fsme-0.9/ui' /usr/share/qt3/bin/uic neweiobasedlg.ui -o .ui/neweiobasedlg.h /usr/share/qt3/bin/uic eiobasedlg.ui -o .ui/eiobasedlg.h /usr/share/qt3/bin/uic statedlg.ui -o .ui/statedlg.h /usr/share/qt3/bin/uic transitiondlg.ui -o .ui/transitiondlg.h uic: File generated with too recent version of Qt Designer (3.3 vs. 3.2.3) make[1]: *** [.ui/transitiondlg.h] Ошибка 1 make[1]: Leaving directory `/home/jk/tmp/fsme/fsme-0.9/ui'

Санек, ты на сайте 0.7 на 0.9 забыл заменить ;)..

> клетку, в которой будут усыплять жирафа и бегемота

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

А почему в теме KDE? Оно ж вроде только QT требует? Или QT == KDE уже?

>А почему в теме KDE? Оно ж вроде только QT требует? Или QT == KDE уже? Потому что, в отличии от LinuxRuNet, тут нет темы "для разработчика", а у местного окружения именно такое впечатление и есть :-)

Исправь в ui файлах версию 3.3.1 на 3.2 и всё пойдет

>Не собирается под debian/sid. а насколько я помню, там пакет qt самый новый был всегда, в sid-то...

Так что лечится либо upgrade'ом qt, либо правкой версий. По моему, ничего кардинально нового в ui не появилось... но правка

>Санек, ты на сайте 0.7 на 0.9 забыл заменить ;)..

Спасибо, заменил :-)

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

> А можно для тех кто в танке обяснить

На softcraft.ru почитай

>> "А можно для тех кто в танке обяснить (или кинуть ссылку) зачем это нужно и что это делает на практике?"

1) Нужно это, по всей видимости, для того чтобы афтару сдать курсовик в универе.

2) На практике эта приблуда позволяет быстро написать программу для помещёния бигимотоф и жерафоф в халадильник.

abbr (Score: 103 MaxScore: 103) (*) (22.04.2004 11:37:10):

>> А можно для тех кто в танке обяснить

> На softcraft.ru почитай

Присоединяюсь -- несмотря на то, что я умею прямо в уме :) минимизировать конечные автоматы, и могу по регекспу построить КА (и наоборот), и знаю, что такое пампинг-лемма для регулярных грамматик -- на softcraft.ru навскидку не разобрался.

Поясните, плз. под КА там имеются в виду именно КА, или некое обобщение (м.б. стековые, ограниченные линейные, машины Тьюринга)? Имеются ли в виду dfa или nfa?

Имхо афтор курсовик не сдаст, т.к. не раскрыта тема взаимоотношений бигимотоф и жерафоф.

>Имхо афтор курсовик не сдаст, т.к. не раскрыта тема взаимоотношений бигимотоф и жерафоф.

Lol :-) только я уже диплом защитил, так что поздно :)

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

Там очень интересные вещи получаются - два режима - синхронный и асинхроннный, неделимость перехода не пустое слово, и т.д., и т.п :-)

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

Посмотри на издевательства над животными и калькулятор. Зря чтоли писал... :-)

>Поясните, плз. под КА там имеются в виду именно КА, или некое обобщение (м.б. стековые, ограниченные линейные, машины Тьюринга)? Имеются ли в виду dfa или nfa?

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

Я предлагаю автоматный подход к написанию логики работы программы, т. е. когда в объекте более одной управляющей переменной. Если делать "как всегда", то управление им несколько осложняется.

Чтобы было проще - нарисуйте граф, повесьте действия на входы в состояния, выходы из состояний, переходы, сгенерируйте текст и будет удобно. Можно, конечно, и руками этот switch накатать, однако не сильно удобно. К тому же тут и перерисовать/перегенерить автомат можно, а руками написанный текст в отдельном файле. Это как .ui файлы в Qt Designer. Тот же выбор: можно интерфейс руками программить, а можно нарисовать. IMHO, второе удобнее, поэтому и делаю FSME.

PS. Стек есть, но в несколько извращённом варианте: Допустим, хочется из состояния A1 попасть в C1, по пути пройдя через B (в B кинуть себе событие и перейти ещё раз), и дополнительно хочется из A2 попасть в C2 через то же B. Обычно B делят на B1 и B2, либо какой-то флажок поднимают, а тут есть возможность при переходе запихать в стек произвольное состояние (тип перехода transite), а когда надо, перейти на него (тие перехода Return). Не очень наглядно, но разгружает схему.

Минимизация автоматов тут ни к селу, ни к городу, потому как хочется не регекс скомпилить, а логику увидеть.

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

Тип автомата, конечно же, dfa. Только вместо символов алфавита на переходах - произвольные булевы формулы из событий и входов (произвольных булевых функций). Это очень подробно описано в книге автора самой SWITCH - технологии - Шалыто (Питерский институт точной механики и оптики)

adarovsky (Score: 103 MaxScore: 103) (*) (22.04.2004 13:09:49):

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

> Там имеются в виду смешанные автоматы, ...

1.

а) Можно (ссылку на?) определение смешанного автомата?

> нарисуйте граф, ...

Орграф, псевдограф, мультиграф? Граф чего (Фейнмановский граф? Free-scale граф :-))? Где модель?

б) Зачем называть некую новую сущность устоявшимся термином (dfa) ?

3. Я не претендую на поистине глубокие знания современной информатики, просто хотел бы пояснения или _конкретной_ ссылки про смешанные автоматы, о которых идет речь. Насколько этот термин общепринят?

>> "когда автомат - сам по мебе задача"

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

adarovsky (Score: 103 MaxScore: 103) (*) (22.04.2004 13:18:32):

> Обычно автоматы == автоматные грамматики, автоматы со стеком == контекстно-свободные грамматики, и всё. А я хочу показать, что не только. Можно и для других задач их использовать.

Они как-нибудь с иерархией Хомского соотносятся?

> Тип автомата, конечно же, dfa. Только вместо символов алфавита на переходах - произвольные булевы формулы из событий и входов (произвольных булевых функций).

То есть, обсуждаемая конструкция ни имеет НИ МАЛЕЙШЕГО отношения ни к конечным автоматам, ни к грамматикам вообще. Зачем же людям мозги пудрить :-) ?

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

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

>а) Можно (ссылку на?) определение смешанного автомата?

Есть машина Мура (Moore machine), есть машина Мили (Meely machine). Если их смешать, будет смешанный автомат :-) То есть действия могут выполняться и на состояниях (как при известном извращении понятия машины Мура) и на переходах (как у машины Мили)

>Орграф, псевдограф, мультиграф? Граф чего (Фейнмановский граф? Free-scale граф :-))? Где модель?

мультиграф. с петлями. то есть псевдограф (вроде) :-). А причём тут фейнмановская диаграмма?

>б) Зачем называть некую новую сущность устоявшимся термином (dfa) ?

Потому что при известном состоянии и событии известно состояние, куда мы придём. Хотя с введением стека это стало не так :-) Так что с классификацией пока трудности :-)

>3. Я не претендую на поистине глубокие знания современной информатики, просто хотел бы пояснения или _конкретной_ ссылки про смешанные автоматы, о которых идет речь. Насколько этот термин общепринят?

Кроме книги "Swtich-технология" нигде не встречал

PS. Сам все термины нафиг позабывал :-) Приходится лазить по поисковикам, а то будет как в том анекдоте про завод, где запретили матом ругаться )

2adarovsky (Score: 103 MaxScore: 103) (*) (22.04.2004 13:48:53):

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

Если я напишу анонс на программу, решающую 3SAT за линейное время, а потом выяснится, что под 3SAT я имел в виду задачу очередности связи с тремя спутниками...

>Это в смысле, что сайт я посмотрел и сильно сомневаюсь чтобы от этой программы реально могла бы кому-то выйти польза.

А я и не настаиваю. Лично мне она пользу приносит. Никого силой туда не затягиваю.

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

Я с чистой совестью передрал определения из книги Шалыто :-) Я думал, что доктор наук не будет пользоваться неправильной терминологией. Другое дело, что он эту SWITCH-технологию пристраивал в довольно объёмной книге, так что путаница с понятиями может возникнуть. Но говорю опять: это не научная работа, и мне её не защищать, так что я не сильно волнуюсь за терминологию. Главное в проекте - удобство программирования.

А редактор-таки конечных автоматов, потому как есть и события (пусть алфавит), начальное состояние, пустое множество конечных состояний, и собсно состояния и переходы. При желании можно сказать, что алфавит - это множество истинных значений всех булевых формул на переходах, но зачем такие сложности? :-) Редактор автоматов и всё :)

>То есть, обсуждаемая конструкция ни имеет НИ МАЛЕЙШЕГО отношения ни к конечным автоматам, ни к грамматикам вообще. Зачем же людям мозги пудрить :-) ?

Извините! :-) Нигде не говорится, что КА применяются _только_ в грамматиках! Да, там они себя зарекомендовали, однако, если взять книгу Ахо про КА, мы квидим там диаграммы (про супермаркеты пример, по-моему), которая _очень_ напоминает то, что редактируется в топике :-)

<проповедь> Я хочу показать иное, и, смею надеяться, более жизненное применение замечательной абстракции под названием конечный автомат. А если точнее, то с каждым разом я всё больше вижу случаи, когда применение автоматов могло упростить задачу, но их там не было.

Программировать надо с явным выделением состояний системы (C) Шалыто, и волосы будут мягкими и шелковистыми :-))))

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

PS. В книге по OpenGL сказано, что она - конечный автомат. Это я к тому, что не я тут всякую муть придумываю, её говорят люди с авторитетом, а я их этим самым авторитетом пытаюсь отбиваться :-) Если надо, можете ссылки поискать, я не вру, когда на Шалыто и OpenGL ссылаюсь. Книга по OpenGL - которая библия

</проповедь>

>взаимоотношений

Слово то какое нашёл :)))) (c) старый анектод

>PS. В книге по OpenGL сказано, что она - конечный автомат.

OpenGL, а не книга :-)

А графы ты как рисуешь - библиотеку специальную нашел, или сам написал? - если сам, то насколько она функциональная и насколько независима от основного проекта?

Аминь.

Че ты оправдываешься как маленький? Написал и работает - значит молодец.

Ты че не читал "Физики шутят?", наипервейший приемчик против аппонента -

обвинение в неправильном использовании терминологии.

Когда искал - не было. Сам писал. Отдельно можно использовать, но она кривая. Писал давно, надо переделывать. Хотя, может я и зря так.

Она использует Qt Canvas. В Canvas нет элементов типа полилиний, сложных элементов (например, стрелка - это полилиния и указатель. Родишься от неё - можно ещё элементов добавлять, менять её вид, и т.д.). Узлы - не только квадраты. По идее, можно сделать произвольной формы. То есть, расниряемая вещь. Попробуй, может понравится.

Ну дураком же не называют - вопросы задают. Я и отвечаю по мере способностей :-)))

Берётся просто - это каталог diagram. Есть и ещё одна интересная вещь там - это фабрика действий. Тоже довольно независимая вещь. Реализует Undo/Redo. Файлы action.* actionfactory.* browseable.*, короче то, что в kernel валяется. Только его почистить надо будет.

>Они как-нибудь с иерархией Хомского соотносятся?

Никак. Грамматики с реактивными системами по-моему не пересекаются

Sun-ch (Score: 104 MaxScore: 105) (*) (22.04.2004 14:49:00):

> наипервейший приемчик против аппонента - обвинение в неправильном использовании терминологии.

Дык - я, вроде, хотя и обвиняю, но -- не оппонент. Вполне себе интересный проект...

2adarovsky:

Дык - хозяин -- барин...

Я ж просто совет дал. Если охота плодить недоразумения, замешанные на нетрадиционной терминологии -- вперед!

А многопоточность принципиальна для FSME? У меня qt без потоков откомпилирована.
FSME не собирается. А перекомпилировать Qt сейчас нет возможности.

>А многопоточность принципиальна для FSME? У меня qt без потоков откомпилирована.

Да нет вообще-то. thread из .pro можно смело выкинуть. Нитей пока нет. Просто оно у них однопоточное deprecated, я и не заморачивался на эту тему.

>Да нет вообще-то. thread из .pro можно смело выкинуть. Нитей пока нет. Просто оно у них однопоточное deprecated, я и не заморачивался на эту тему.

Тогда лучше так (в .pro):
exists( $(QTDIR)/lib/libqt-mt* ) {
message( "Configuring for multi-threaded Qt..." )
CONFIG += thread
}

для тех кто в танке, автоматный подход можно использовать где угодно, в обсуждении FSME-0.7 (http://www.linux.org.ru/profile/filin/view-message.jsp?msgid=525974&back=...) я уже давал ссылку на ресурс: http://www.softcraft.ru/auto.shtml

начните читать например отсюда: http://www.softcraft.ru/design/ap/ap01.shtml

Благодарю за информацию, буду изучать.

Ок, исправляю

>А можно для тех кто в танке обяснить (или кинуть ссылку) зачем это нужно и что это делает на практике?

В дополнение к примерам я написал Online Tutorial: http://fsme.sourceforge.net/doc/tutorial.html

adarovsky, Die-Hard, чтобы уточнить терминологию о графах посмотрите книги по дискретной математике (например Новикова (новая книга) или Ерусалимского (довольно старая). Скорее всего терминологию конечных автоматов можно посмотреть в книге Ахо, Сети, Ульман - Компиляторы: Принципы, технологии, инструменты (хотя это немного не по теме).
Все вышеуказанные книги можно скачать (в формате DjVu) с сайта http://books.forcesite.ru/cgi-bin/catalog.cgi Там ещё много интересных книг (в основном физ-мат.).
P.S. Я не автор вышеуказанного сайта, просто хочу поделиться полезной ссылкой.