В Глушкове необходимо ограничить метод только для 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-однозначна.
В Глушкове необходимо ограничить метод только для 1-однозначных регулярок. Потому что иначе получится вот такая ерунда, как в примере ниже
Линеаризуем:
(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-однозначна.