Эквивалентность конечных автоматов
Originally reported on Google Code with ID 81
Реализовать функцию определения эквивалентности конечных автоматов в новом, стаднартизированном
формате.
Reported by oasychev
on 2011-12-30 13:03:37
Comments (9)
-
reporter -
reporter ``` Только алгоритм надо доработать для определения эквивалентности подмасок, а это не совсем тривиально... ```
Reported by `oasychev` on 2012-01-05 11:19:55
-
``` Еще пара ссылок, с возможно более понятными объяснениями
http://ecommons.cornell.edu/bitstream/1813/5958/1/71-114.pdf То же самое в виде презентации с картинками: http://drona.csa.iisc.ernet.in/~deepakd/atc-2009/Vijeth-Chintan-Seminar.pdf
Еще немного полезностей: https://ritdml.rit.edu/bitstream/handle/1850/8712/DNortonMastersProject03-2009.pdf
Я бегло пробежался по ним и мне кажется, что придется сначала строить ДКА, и потом проверять эквивалентность. По крайней мере, в последней ссылке упоминается необходимость конвертирования. ```
Reported by `vostreltsov` on 2012-01-05 19:34:22
-
reporter ``` Основная проблема эквивалентности - это то, что нам нужно определить эквивалентность не только по принятию/отклонению - но и по подмаскам.
А тут уже гораздо сложнее, т.к. даже сам их формат хранения в ДКА совсем другой. И боюсь что большинство опубликованных алгоритмов эквивалентности этого не учитывает, придется думать самим. ```
Reported by `oasychev` on 2012-01-06 12:54:03
-
reporter ``` Валерий, вы можете оценить какой из алгоритмов эквивалетности наиболее перспективен с точки зрения дальнейшей доработки по определению эквивалентности подмасок? ```
Reported by `oasychev` on 2012-01-18 09:59:37
-
reporter Новый владелец задачи
Reported by
oasychev
on 2013-07-25 22:38:16 -
reporter Камо, вот это issue может содержать дополнительные полезные материалы...
Reported by
oasychev
on 2015-03-01 22:30:06 -
reporter Issue 287 has been merged into this issue.
Reported by
oasychev
on 2015-03-01 22:36:46 -
reporter -
assigned issue to
- edited description
При переносе на битбакет потеряло владельца...
-
assigned issue to
- Log in to comment
``` Эквивалентность конечных автоматов http://web.science.mq.edu.au/~chris/langmach/chap05.pdf
```
Reported by `oasychev` on 2011-12-30 13:03:59