 |
|
|
 
|
|
эквивалентность пар состояний в КА, в детерминированных конечных автоматах 
| silverghost |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 11.12.2005 Где: Россия, Тольятти Репутация: нет Всего: нет |
Здравствуйте, нужна помощь в реализации алгоритма определения эквивалентности пар состояний в детерминированном конечном автомате. Встает еще вопрос задания этого самого конечного автомата.
Например, есть A Linear Algorithm for Testing Equivalence of Finite Automata ( John E. Hopcroft and R. M. Karp) Может у кого-нить есть какие-нить примерные наработки или посоветуйте литературку  |
|||
|
||||
Загрузка ...
| SoWa |
|
|||
 Харекришна  Профиль Группа: Комодератор Сообщений: 2422 Регистрация: 18.10.2004 Репутация: 6 Всего: 74 |
Не понимаю. Давно я правда не занимался автоматами, но разве они не едино задаются последовательностью переходов? Вроде матрица переходов строится. В книжках должно быть. А вообще ищи в Кормене. Там все есть Еще книжка есть(djvu) "Автоматы" автор Карпов. Там ищи теорему Мура. Гилл. "Введение в теорию конечных автоматов". Тоже djvu. Русскоязычные все. Удачи в поисках -------------------- Всем добра  |
|||
|
||||
| Artemios |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 405 Регистрация: 14.8.2006 Где: Саратов, Россия Репутация: 1 Всего: 50 |
Неплохие алгоритмы минимизации автоматов по эквивалентным и толерантным состояниям есть в книге
"Дискретная математика для инженера" автора непомню, формат djvu. (соответственно там же и разбиение множества состояний на эквивалентные либо толерантные классы) Добавлено @ 01:02 Ой, или "Математический аппарат инженера"... точно не помню  -------------------- fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ] |
|||
|
||||
| maggot |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 21 Регистрация: 15.1.2007 Репутация: нет Всего: нет |
Если тебе нужен просто алгоритм генерации ДКА, то вот, там алгоритм есть http://www.codeproject.com/cpp/OwnRegExpressionsParser.asp
|
|||
|
||||
| silverghost |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 11.12.2005 Где: Россия, Тольятти Репутация: нет Всего: нет |
2SoWa:
Да под заданием ДКА как раз подразумевалась генерация, извините, не правильно выразилась. 2maggot: Спасибо за ссылку Может кто-нибудь знает где можно найти статью из журнала "Theoretical Computer Science" за февраль 2005 года? Интересует статья Jean-Marc'a Champarnaud'a и Thomas'a Paranthoën'a "Random generation of DFAs". |
|||
|
||||
| silverghost |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 19 Регистрация: 11.12.2005 Где: Россия, Тольятти Репутация: нет Всего: нет |
||||
|
||||
может кому еще пригодиться 
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0642 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |