Поддержка отрицания в to_glushkov и to_ilieyu

[xendalm]

No description provided.

[TonitaN]

В Глушкове необходимо ограничить метод только для 1-однозначных регулярок.
Потому что иначе получится вот такая ерунда, как в примере ниже

(aa|ab)*a

Линеаризуем: (a1 a2 | a3 b4)* a5. Очевидно, NotFirst(r)={b}, и на этом этапе всё нормально. Но затем: NotFollow(a1)={b}, NotFollow(a3) = {a}, и вуаля, мы добавляем в дополнение те же переходы, которые есть в исходном автомате, и дальше якобы в автомате дополнении (по алгоритму из статьи Gelade&Neven) можно читать любой суффикс. Хотя тут очевидно, что нет.

Поэтому скажем, что регулярка 1-однозначна, если для каждых двух альтернативных переходов их first-множества алфавитно не пересекаются. И только для таких регулярок будем строить Глушкова с отрицанием.

При этом First(^r), где r --- 1-однозначная регулярка, будет определяться как объединение NotFirst(r) и First(r'), где r' определяется по конструкции Gelade&Neven. При этом возникнет мощное упрощение: если отрицание регулярки конкатенируется с чем-то ещё, то такое возможно с сохранением 1-однозначности только если NotFirst(r) и NotFollow(ri) (для всех ri) пусто. Иначе будет неоднозначный переход, и можно смело отказываться от построения автомата Глушкова по причине того, что регулярка не 1-однозначна.