remove_eps fix

[shevchenkokk]

Переделал метод remove_eps. Теперь состояния из eps-замыкания объединяются в одно.

@xendalm, на новом remove_eps не проходят тесты из test_ambiguity, поэтому нужно пересмотреть их и поправить, если всё ок.

[shevchenkokk]

@TonitaN, должен ли метод оставлять автомат, в котором нет eps-переходов, в исходном виде? Пример работы в текущей реализации:

[TonitaN]

Ну тут же нет эпсилон-замыканий как таковых, то есть состояния не должны меняться. У меня есть предложение сделать 2 варианта (что добру пропадать): старый индусский RemEps и новый алгебраический RemEps. Можно назвать их RemEps+ и RemEps - потому что, заразы, они в разных учебниках по-разному описываются! То есть нет единого мнения, как должен выглядеть алгоритм удаления эпсилон-переходов. Так что в произошедшем нет вины @xendalm или вас - если уж авторы учебников не могут согласовать между собой вопрос, как удалять эпсилон-переходы, то куда уж нам, смертным.

[xendalm]

А если рассматривать новый алгебраический, в этом примере должны сливаться состояния или нет? Кирилл говорит, что если следовать алгоритму, то даже автоматы без eps-переходов будут меняться

[TonitaN]

Не должны, ведь здесь нет перестройки структуры состояний. Переходы будут модифицированы только в том случае, если модифицируется состояние (строятся эпсилон-замыкания состояний).

[shevchenkokk]

Мои попытки построить аналогичный автомат без eps-переходов не увенчались успехом( Хотя с eps-переходами все обрабатывается вроде нормально.

В примере выше имеем:

ε-closure {s} = s ε-closure {δ(s, a)} = ε-closure {a.0, a.1} = {a.0, a.1}.

Собственно, получаем новое объединённое состояние. Вопрос в том, что же я делаю не так...

[TonitaN]

Ну если верить теории, то эпсилон-замыкание делаем по состоянию. Потом из эпсилон-замкнутого состояния строим переход в эпсилон-замыкания всех состояний по некоторой букве. То есть будет так:

s' = eps-closure {s} = s
delta (s', a) = {eps-closure{a.0}, {eps-closure{a.1}}}

Поскольку они замыкаются сами собой, то останется два перехода.

[TonitaN]

При такой модификации эпсилон-замыкание на автоматах без эпсилон-переходов всегда будет тождественным преобразованием. А вот на автоматах с эпсилон-переходами будут изменения.

[shevchenkokk]

Теперь всё встало на свои места. Спасибо!

[TonitaN]

И гипотеза про Глушкова работает? 🥰

[TonitaN]

В этой ветке нет верификатора пока (и сливать немного больно, т.к. на фронтенде уже 100500 новых коммитов с тех пор). У вас получилось найти контрпример к Глушкову = Томпсону без эпсилонов?

UPD - а нет, есть, со старыми логами. Вроде 100% у меня?... Сейчас на 1000 запустила.

[xendalm]

Глушкова я проверил, работает. А вот с ilieyu, у нас размечаются eps на недетерминированных переходах, из-за чего после не убираются. Но это уже другая история...

[xendalm]

В принципе можно сделать удаление размеченных eps, но как бы я чего не сломал. А так вообще уже можно слить