Как всем известно, регулярные выражения с точки зрения теории формальных языков задаются через символы языка и операторы конкатенации, объединения и повторения. Поскольку регулярные языки (задаваемые регулярными выражениями) замкнуты не только относительно данных операций, но ещё и относительно операций дополнения, вычитания и пересечения, расширим регулярные выражения так, чтобы их можно было задавать через операторы
— конкатенация
— объединение
— повторение
— дополнение
— вычитание
— пересечение
— обращение
Хочется иметь алгоритм, который будет
— эффективно (значит быстро работать на практике*) строить по данному расширенному выражению детерминированный конечный автомат.
— вычислять является ли пустым язык, задаваемый расширенным регулярным выражением.
*Вообще, можно на каждое подвыражение строить автоматы, и выполнять операции над ними, но это медленно.
Интересует литература, где бы это могло быть описано. В "классических" книгах описаны только доказательства того, что класс регулярных языков замкнут относительно этих операций. Мне же нужны эффективные алгоритмы, а не доказательства.
ДКА можно строить из регулярно выражения путем построения промежуточного НКА. Как нужно расширить НКА для того чтобы получать его из расширенного операциями (дополнение, вычитание, пересечение) регулярного выражения за линейное время? Видимо нужны какие то дополнительные типы переходов между состояниями.
Здравствуйте, Aleх, Вы писали:
A>ДКА можно строить из регулярно выражения путем построения промежуточного НКА.
Есть хорошие алгоритмы по построению ДКА по регулярному выражению и без этого шага.
A>Как нужно расширить НКА для того чтобы получать его из расширенного операциями (дополнение, вычитание, пересечение) регулярного выражения за линейное время?
За линейное время от чего?
Если у тебя есть автоматы с числом состояний m и n для двух каких-то регулярных выражений, то автомат, принимающий пересечение соответствующих языков, может иметь mn состояний. В качестве примера можно рассмотреть пару РВ: (aaaa)* и (aaaaa)*, у которой в результате пересечения получиться длинное РВ (aaaaaaaaaaaaaaaaaaaa)* с автоматом, у которого также будет много состояний.
То есть твои расширенные регулярные выражения могут приводить к комбинаторному взрыву. Получается, что алгоритма построения ДКА/НКА с линейным от размера входа временем работы не существует, ибо сам размер выходного автомата велик.
Разумеется, ты можешь сделать расширенный-НКА чтобы уметь делать то же пересечение быстро. Но это лишь откладывание проблемы на потом, ибо расширенный-НКА в ДКА придётся преобразовывать другим алгоритмом, который всё также будет вынужден иметь дело с огромным числом состояний (которых будет куда больше чем при преобразовании обычного НКА в ДКА).
Здравствуйте, Aleх, Вы писали:
A>Как всем известно, регулярные выражения с точки зрения теории формальных языков задаются через символы языка и операторы конкатенации, объединения и повторения. Поскольку регулярные языки (задаваемые регулярными выражениями) замкнуты не только относительно данных операций, но ещё и относительно операций дополнения, вычитания и пересечения, расширим регулярные выражения так, чтобы их можно было задавать через операторы A>- конкатенация A>- объединение A>- повторение A>- дополнение A>- вычитание A>- пересечение A>- обращение
A>Хочется иметь алгоритм, который будет A>- эффективно (значит быстро работать на практике*) строить по данному расширенному выражению детерминированный конечный автомат.
Это невозможно. Операции над регулярнвми языками могут приводить к экспоненциальному росту числа состояний автомата.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Aleх, Вы писали:
A>>ДКА можно строить из регулярно выражения путем построения промежуточного НКА. W>Есть хорошие алгоритмы по построению ДКА по регулярному выражению и без этого шага.
A>>Как нужно расширить НКА для того чтобы получать его из расширенного операциями (дополнение, вычитание, пересечение) регулярного выражения за линейное время? W>За линейное время от чего? W>Если у тебя есть автоматы с числом состояний m и n для двух каких-то регулярных выражений, то автомат, принимающий пересечение соответствующих языков, может иметь mn состояний. В качестве примера можно рассмотреть пару РВ: (aaaa)* и (aaaaa)*, у которой в результате пересечения получиться длинное РВ (aaaaaaaaaaaaaaaaaaaa)* с автоматом, у которого также будет много состояний. W>То есть твои расширенные регулярные выражения могут приводить к комбинаторному взрыву. Получается, что алгоритма построения ДКА/НКА с линейным от размера входа временем работы не существует, ибо сам размер выходного автомата велик.
Алгоритма построения ДКА разумеется не существует. W>Разумеется, ты можешь сделать расширенный-НКА чтобы уметь делать то же пересечение быстро. Но это лишь откладывание проблемы на потом, ибо расширенный-НКА в ДКА придётся преобразовывать другим алгоритмом, который всё также будет вынужден иметь дело с огромным числом состояний (которых будет куда больше чем при преобразовании обычного НКА в ДКА).
Именно это я и хочу. На итоговую оценку сложности это не должно повлиять. Дело в том, что если я буду создавать конечный автомат для каждого подвыражения и объединять сами автоматы (заданные стандартным образом), для каждой операции пересечения нужно будет полностью перестраивать автомат. При реализации этого на языке программирования, будет много выделений памяти.
Вообще задача такая. Строятся различные регулярные выражения, используя в том числе операции пересечения и вычитания. После этого нужно для заданных двух выражений определять дают ли они в пересечении пустой язык или нет.
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, Aleх, Вы писали:
A>>Хочется иметь алгоритм, который будет A>>- эффективно (значит быстро работать на практике*) строить по данному расширенному выражению детерминированный конечный автомат.
Ш>Это невозможно. Операции над регулярнвми языками могут приводить к экспоненциальному росту числа состояний автомата.
Понятно, что в итоге состояний может быть экспоненциальное число. Хочется в промежуточных выражениях выполнять операции пересечения быстро.
A>Вообще задача такая. Строятся различные регулярные выражения, используя в том числе операции пересечения и вычитания. После этого нужно для заданных двух выражений определять дают ли они в пересечении пустой язык или нет.
Хороший пример PSPACE-complete задачи. Ну удачи тебе в поиске быстрого решения :)
A>Именно это я и хочу. На итоговую оценку сложности это не должно повлиять.
О какой оценке ты говоришь? Там как требовалось огромное число действий, так и будет требоваться.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Aleх, Вы писали:
A>>Вообще задача такая. Строятся различные регулярные выражения, используя в том числе операции пересечения и вычитания. После этого нужно для заданных двух выражений определять дают ли они в пересечении пустой язык или нет. W>Хороший пример PSPACE-complete задачи. Ну удачи тебе в поиске быстрого решения
Под поиском быстрого решения я имею ввиду быстрый на практике алгоритм. Понятно, что даже построение Детерминированного конечного автомата имеет сложность O(2^n). При этом для регулярных выражений, используемых на практике, время построения обычно не достигает теоретической оценки.
A>>Именно это я и хочу. На итоговую оценку сложности это не должно повлиять. W>О какой оценке ты говоришь? Там как требовалось огромное число действий, так и будет требоваться.
Я говорю о том, что на теоретическую оценку не повлияет, если каждый символ превратить в тривиальный конечный автомат и выполнять операции объединения, пересечения и конкатенации над автоматами, либо же строить результирующий автомат сразу по регулярному выражению. Кажется, что второй способ быстрее на практике.
