Эквивалентность конечных автоматов

[Oleg Sychev]

Originally reported on Google Code with ID 81

Реализовать функцию определения эквивалентности конечных автоматов в новом, стаднартизированном
формате.

Reported by oasychev on 2011-12-30 13:03:37

[Oleg Sychev]

``` Эквивалентность конечных автоматов http://web.science.mq.edu.au/~chris/langmach/chap05.pdf

```

Reported by `oasychev` on 2011-12-30 13:03:59

[Oleg Sychev]

``` Только алгоритм надо доработать для определения эквивалентности подмасок, а это не совсем тривиально... ```

Reported by `oasychev` on 2012-01-05 11:19:55

[Valeriy Streltsov]

``` Еще пара ссылок, с возможно более понятными объяснениями

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

[Oleg Sychev]

``` Основная проблема эквивалентности - это то, что нам нужно определить эквивалентность не только по принятию/отклонению - но и по подмаскам.

А тут уже гораздо сложнее, т.к. даже сам их формат хранения в ДКА совсем другой. И боюсь что большинство опубликованных алгоритмов эквивалентности этого не учитывает, придется думать самим. ```

Reported by `oasychev` on 2012-01-06 12:54:03

[Oleg Sychev]

``` Валерий, вы можете оценить какой из алгоритмов эквивалетности наиболее перспективен с точки зрения дальнейшей доработки по определению эквивалентности подмасок? ```

Reported by `oasychev` on 2012-01-18 09:59:37

[Oleg Sychev]

Новый владелец задачи

Reported by oasychev on 2013-07-25 22:38:16

[Oleg Sychev]

Камо, вот это issue может содержать дополнительные полезные материалы... 

Reported by oasychev on 2015-03-01 22:30:06

[Oleg Sychev]

Issue 287 has been merged into this issue.

Reported by oasychev on 2015-03-01 22:36:46

[Oleg Sychev]

При переносе на битбакет потеряло владельца...