Программистская игрушка

[plakhov]

Придумал очень красивую штуку, чисто программистскую, остальным будет неинтересно.

Каждому программисту известно, что такое регулярные выражения. Каждому человеку, прошедшему базовый курс CS, известно, что базовые регулярные выражения (без backtracking-а) хорошо моделируются недетерминированными конечными автоматамиВ интересах этой записи

Comments

[lightscore]

блин, красиво!

(только ссылка из второго абзаца в хроме/фф не открывается. открывается вот такая https://swtch.com/~rsc/regexp/regexp1.html)

[plakhov]

Я поправил, спасибо!

[fat_crocodile]

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

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

А*, насколько я помню, требует эвристику, а так же известные начало и конец. Тут же задача явно сформулирована более общё. Например, регэксп может начинаться с .*, и мы сразу получаем все пути, какие есть.

[fat_crocodile]

То есть, если у нас фиксировано начало и запретить циклы, то получится хитрый Дейкстра, и я почти верю, что это будет работать за "количество ребер" * "длина регэкспа".

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

[plakhov]

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

Сначала алгоритм узнаёт, что начальная вершина достижима в стартовом состоянии. Каждый раз, устанавливая факт "оказывается, вершина V достижима в новом состоянии S", он исследует следствия из этого знания для ее ближайших соседей; если он уже знал, что пара (V,S) достижима, то ничего делать не нужно. Таким образом каждую вершину V надо посетить не более |S| раз.

[fat_crocodile]

Представляя, как я бы это делал: если состояние вершины (= список состояний НКА, в котором он может находиться в этой вершине) изменилось, нам надо обойти всех её соседей, то есть степень вершины.

Состояния вершин может меняться не более чем n раз, значит для каждой вершины получаем n * степень. Сумма по всем вершинам это что-то типа 2nE, где E это количество ребер, а 2 если ребра ненаправленные.

Да, это гораздо лучше, чем я подумал. Круто!

[lyuden]

Там в ссылке "~rsc" должно быть, вместо "~rsС"

У меня во всяком случае прямо из поста не открывается.

[ext_5701641]

У вас есть проблема. Вы решили ее регулярными выражениями. Теперь у вас две проблемы.

[plakhov]

...теперь у вас одна или более проблемы подряд

[levgilman]

S(0*|0*K(0|K|D)*)F - первый 0, кажется, лишний? Просто S0*K(0|K|D)*F разве не то же самое?

[plakhov]

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

[levgilman]

Да, ошибся . Тогда S0*(K(0|K|D)*)?F
(можно заменить ? на * - будет корректно, но некрасиво)

[plakhov]

Да, так можно