search

OnionGrief / Chipollino

преобразования регулярных выражений и конечных автоматов
Other
18 stars 4 forks source link

Методы MFA #315

Closed xendalm closed 8 months ago

xendalm commented 8 months ago

@TonitaN, знаю, что спросил про приоритеты и сделал все ровно наоборот... Осталось дописать прошлогодний диплом(

TonitaN commented 8 months ago

Удалось разобраться с принимающими-не принимающими ловушками по Шмиду?

xendalm commented 8 months ago

Удалось разобраться с принимающими-не принимающими ловушками по Шмиду?

А на что это должно было повлиять?

TonitaN commented 8 months ago

Удалось разобраться с принимающими-не принимающими ловушками по Шмиду?

А на что это должно было повлиять?

В принципе на дополнения, если есть переходы по читающим веткам. Но завтра я попробую посмотреть, насколько это актуально именно сейчас.

TonitaN commented 8 months ago

А таки несколько быстрее экспериментальный MFA, чем обычный, построенный по рекурсивному алгоритму.

С дополнением таки потребуется дополнительная работа, в том числе из-за эпсилон-переходов (а ещё из-за пустой памяти). Их придётся устранить, причём предлагаю - простейшим методом, который строит по каждой композиции эпсилон-перехода с переходом по t единственный переход с меткой t. При этом действия над памятью умножаются: единственный нетривиальный случай умножения, если по эпсилон-переходу память закрывается, а по t -- открывается. Это означает, что мы можем игнорировать закрытую по эпсилон-переходу память (она сразу перезапишется) и сразу её открыть. Остальные случаи понятны: если действия одинаковы (два открытия подряд), то можно оставить одно; два закрытия подряд идти не могут; иначе переносим то действие, которое как-то меняет состояние ячейки памяти.

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

Очень хорошо было бы сделать генератор случайных ref-слов, чтобы добавить метаморфные тесты - через обычные юнит-тесты не очень просто отслеживать всё сразу.

TonitaN commented 8 months ago

И пора мало-мальски добавлять MFA в интерпретатор, чтобы иметь возможность тестировать логирование. Можно максимально базово пока.

xendalm commented 8 months ago

Их придётся устранить, причём предлагаю - простейшим методом, который строит по каждой композиции эпсилон-перехода с переходом по t единственный переход с меткой t. @TonitaN

В итоге все равно реализовал алгоритм с "eps-замыканиями" (может это и подразумевалось...), тк цепочки eps-переходов возможны. Но с ограничением на количество переходов по одному символу (в т.ч. eps) до 1. Для complement этого достаточно

И пора мало-мальски добавлять MFA в интерпретатор, чтобы иметь возможность тестировать логирование. Можно максимально базово пока.

Попробуем с @mathhyyn через DSL