Например, есть http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR71-114 ( John E. Hopcroft and R. M. Karp)
Может у кого-нить есть какие-нить примерные наработки или посоветуйте литературку
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > эквивалентность пар состояний в КА |
| Автор: silverghost 20.1.2007, 20:37 |
| Здравствуйте, нужна помощь в реализации алгоритма определения эквивалентности пар состояний в детерминированном конечном автомате. Встает еще вопрос задания этого самого конечного автомата. Например, есть http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR71-114 ( John E. Hopcroft and R. M. Karp) Может у кого-нить есть какие-нить примерные наработки или посоветуйте литературку |
| Автор: SoWa 20.1.2007, 21:12 | ||
Не понимаю. Давно я правда не занимался автоматами, но разве они не едино задаются последовательностью переходов? Вроде матрица переходов строится. В книжках должно быть. А вообще ищи в Кормене. Там все есть Еще книжка есть(djvu) "Автоматы" автор Карпов. Там ищи теорему Мура. Гилл. "Введение в теорию конечных автоматов". Тоже djvu. Русскоязычные все. Удачи в поисках |
| Автор: Artemios 21.1.2007, 01:01 |
| Неплохие алгоритмы минимизации автоматов по эквивалентным и толерантным состояниям есть в книге "Дискретная математика для инженера" автора непомню, формат djvu. (соответственно там же и разбиение множества состояний на эквивалентные либо толерантные классы) Добавлено @ 01:02 Ой, или "Математический аппарат инженера"... точно не помню  |
| Автор: maggot 1.2.2007, 16:06 |
| Если тебе нужен просто алгоритм генерации ДКА, то вот, там алгоритм есть http://www.codeproject.com/cpp/OwnRegExpressionsParser.asp |
| Автор: silverghost 18.3.2007, 12:50 |
| 2SoWa: Да под заданием ДКА как раз подразумевалась генерация, извините, не правильно выразилась. 2maggot: Спасибо за ссылку  Может кто-нибудь знает где можно найти статью из журнала "Theoretical Computer Science" за февраль 2005 года? Интересует статья Jean-Marc'a Champarnaud'a и Thomas'a Paranthoën'a "Random generation of DFAs". |
| Автор: silverghost 18.3.2007, 21:33 |
 может кому еще пригодиться http://paranthoen.thomas.free.fr/PAPERS/RandDFAToAppearInTCS.ps.gz |
