Monoid refactor

[xtoter]

Тут буду потихоньку собирать запоздалые фиксы моноида

[xtoter]

• [x] Переписать на эффективный алгоритм
• [x] Потеря классов эквивалентности
• [x] Минимальность (ловушки)
• [x] Адекватная работа для НКА
• [ ] Логи

UPD.

• [x] Разобраться с НКА

[xtoter]

Пока не нашел примера который бы терял классы эквивалентности, старые примеры начали проходить. Также из-за другого способа поиска эквивалентных состояний в новом алгоритме вроде адекватно работает для НКА (и без eps переходов), по крайней мере мне пока не удалось сломать. Пример приведенный в (#199) у меня строится моментально.

[TonitaN]

Проверьте, пожалуйста, на подопытной регулярке и автомате:

R = ab(bc|ca|)(ab|bc|ca|a)*bab(bc|ca|ab|cb|ac)*
A1 = Reverse.MergeBisim.Reverse.MergeBisim.IlieYu R !!
A2 = Minimize.Determinize.Glushkov R !!

До рефакторинга трансмоноид считался для минимального ДКА ночь, и результата дождаться не удалось всё равно. Сколько сейчас получается по времени?

[mathhyyn]

сегодня мы этого не узнаем

R = {ab(bc|ca|)(ab|bc|ca|a)*bab(bc|ca|ab|cb|ac)*}
A1 = Reverse.MergeBisim.Reverse.MergeBisim.IlieYu R !!
A2 = Minimize.Determinize.Glushkov R !!
A3 = MyhillNerode A2 !!

[xtoter]

До рефакторинга трансмоноид считался для минимального ДКА ночь, и результата дождаться не удалось всё равно. Сколько сейчас получается по времени?

A1 = Reverse.MergeBisim.Reverse.MergeBisim.IlieYu R !! - для этого считается необозримо долго (на час запустил, перебирает слова длины 17 и конца не видно ¯_(ツ)_/¯) судя по картинке там много чего

A2 = Minimize.Determinize.Glushkov R !! тут уже лучше, я на самом деле не знаю каков должен быть адекватный результат, но вроде время нормальное (фотопруф) UPD. вроде исправил багу с вылетом на винде

[TonitaN]

Ну там в минимальном ДКА больше 20 состояний, а в этом НКА всего 9. Интересно, почему на НКА настолько дольше работает?

[xtoter]

12 часов для A1 = Reverse.MergeBisim.Reverse.MergeBisim.IlieYu R !! не дали результата, видимо таки прийдется вводить eps для НКА

[xtoter]

Надеюсь осознал почему так долго строятся некоторые НКА, полюбуйтесь на таблицу переходов(

[xtoter]

Сливать пока не буду (жду логов), но был бы признателен если кто-нибудь потестировал бы, вроде должен был все баги исправить UPD. Логи отдельно пилят, сказали вливать 🙃

[xendalm]

В следующий раз обязательно отмечу, что можно не делить на 11 коммитов

[xtoter]

Зато каждый коммит привязан к изменению🙃

[TonitaN]

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