Фикс извлечения 1-однозначной регулярки

[mathhyyn]

из #212 :

• [ ] 1.

  N2 = Disambiguate {|(a(b*|b*baa)a(|b))*} !!

  получается неэквивалентная регулярка (ab*a|b*ab|b)*

• [ ] 2.

  N1 = Disambiguate {bb*a(|a*|b(a|b(|a)))*} !!
  Equiv {bb*a(|a*|b(a|b(|a)))*} {bb*a(a|b(b*a)((b|a)))*}

  

• [x] Equal сообщает о том, что регулярка не изменилась

из #192

Похоже, что большая часть проблем с 1-однозначными регулярками из Глушкова связана с финальными состояниями. Возможно, если это предположение верно, то помогла бы левая дистрибутивность конкатенации и альтернативы (если бы был рабочий метод Normalize), но нужно ещё проверять.

По ходу дела нашлась лемма, что Арден сохраняет степень однозначности (которая не 1-Unambiguity, а просто Ambiguity) автомата в регулярке. То есть якобы Ambiguity.Glushkov.Arden A1 = Ambiguity A1. Надо будет потом проверить, получается ли у нас так.

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

Тупой рефал-скрипт с парой правил переписывания, кажется, всё вылечил, но нужно ещё проверять. Короче, нужна дистрибутивность слева и перенос звёздочки вперёд (ещё там иногда альтернативы внутри звёздочки после применения дистрибутивности переставляются, это тоже надо учесть). И 1-однозначный Глушков тогда вроде как порождает через Ардена 1-однозначную регулярку.

[TonitaN]

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

[mathhyyn]

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

N1 = Arden.Glushkov {bb*a(|a*|b(a|b(|a)))*} !!
Equiv N1 {bb*a(|a*|b(a|b(|a)))*}

так и есть :(

если убрать кэширование, результат false

[xendalm]

В текущей реализации 1-однозначная регулярка собирается из строк. После введение новой системы разметки alphabet_symbol, это приведет к ошибочной работе метода, если символы размечены. Для решения этой проблемы придётся либо менять парсер регулярок, либо собирать 1-однозначную иначе.

[TonitaN]

На всякий случай лучше парсер поменять когда-нибудь )) В Ардене, может, тоже кто-то захочет через to_str что-то отрефакторить, а ещё Normalise есть, там очень классно использовать рефал-стиль ) (но лучше не надо) Не моё ))