Как можно сопоставить два разных шаблона поиска (regexp1 и regexp2)использующих регулярные выражения, на предмет определения могут ли у них быть общие решения. Т.е. можно ли определить, что существуют (или не могут существовать) наборы данных которые соответствует и выражению regexp1 и regexp2, не для конкретного набора данных а в общем случае.
Например:
regexp1 sample[0-9]+
regexp2 ??mple30
regexp3 = [0-9]+mple??
regexp1 и regexp2 — сопоставляются
regexp1 и regexp3 — не сопоставляются
regexp2 и regexp3 — сопоставляются

каждому регэкспу соответствует конечный автомат.
Можно взять произведение этих автоматов (состояние нового автомата это пара состояний, пара (a,b) переходит в (x,y), если a->x и b->y)
И посмотреть достижимо ли в этом автомате конечное состояние (фактически есть ли путь в нем как в графе).

Здравствуйте, dilmah, Вы писали:

D>каждому регэкспу соответствует конечный автомат.
D>Можно взять произведение этих автоматов (состояние нового автомата это пара состояний, пара (a,b) переходит в (x,y), если a->x и b->y)
D>И посмотреть достижимо ли в этом автомате конечное состояние (фактически есть ли путь в нем как в графе).

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

BNN>данный путь решения не приемлем с практической точки зрения, я бы сказал он "академический",
BNN>даже несложному выражению будет соответствовать конечный автомат с огромным числом состояний, для вычисления которого требуется ресурсы...

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

Здравствуйте, dilmah, Вы писали:


BNN>>данный путь решения не приемлем с практической точки зрения, я бы сказал он "академический",
BNN>>даже несложному выражению будет соответствовать конечный автомат с огромным числом состояний, для вычисления которого требуется ресурсы...

D>сами по себе автоматы не такие и большие. Непрактично большим, действительно, является их произведение, но его не обязательно строить явно, достаточно держать в памяти его сомножители.