Алгоритмические задачки по регулярным выражениям

By On 07.10.2008 · 4 Comments

Накопилась уже множеством. На некоторые я ответы знаю, на некоторые нет.

——

Дано два регулярных выражения.

Необходимо:

1. Определить существуют ли строки к которым подойдут оба из них.

2. Определить конечность и число (в случае конечности) числа строк к которым подойдут оба из них.

3. Сформировать регулярные выражения:

3.1. Охватывающее пересечение двух

3.2. Охватывающее все элементы не входящие в рассматриваемые регулярные выражения

3.3. Охватывающее все элементы подпадающее под одно из выражений выше и не подпадающие под другое.

4. Определить «вложенность» регулярных выражений — все элементы одного входят в набор элементов другого.

5. Решить задачу выше для 3, 4, 5 и n числа регулярных выражений.

Переводя задачи в более общие — регулярные выражения можно заменить на правила в общем случае.

Поделиться в соц. сетях

Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники
Нравится
 
If you enjoyed this article, please consider sharing it!
Reddit Facebook Twitter Delicious
  • Splurov

    Ответы на эти задачи, имея конкретные рег. выражения, должен давать человек, решающий их? Или программа, которую напишет человек и которая будет работать для любых регулярных выражений?

  • http://ivan.begtin.name ivbeg

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

    Приведу пример применимости для некоторых задач из жизни. Есть вырезалка рекламы работающая на регулярных выражениях. Когда добавляют новое выражение необходимо понять нет ли такого выражения в которое полностью входят все его варианты дабы избежать ненужного дублирования сравнений.

  • foldr

    Здесь есть два аспекта — теоретический и практический. С теоретической точки зрения все достаточно просто. Даны два регулярных выражения R1 и R2. Они сводятся к двум детерминированным автоматам (алвафит один и тот же, я его опущу) A1:, A2:. Здесь S — множества состояний, F — функция перехода F:SxE->S (E — алфавит), S1_0 — начальное состояние, T — множества терминальных состояний.

    Построим автомат A: где S=S1xS2, S0=, F:(,a)->, T=T1xT2 (здесь x – это декартово произведение)

    Можно доказать, что постороенный автомат принимает только строки, принадлежащие языку первого И второго автомата, то есть фактически является пересечением двух автоматов A1 и A2. Теперь по автомату строимо регулярное выражение и задача 3.1 решена. Если задать T=(S1\T1)xT2 – то получим автомат, принимающий сторки из языка второго автомата, и не принимающий строки из языка первого – мы решили задачу 3.3

    В полученном автомате не все вершины достижимы. Пусть D(S) – это множество достижимых вершин. Тогда, если D(T1xS2) входит в D(T1xT2) – то язык первого автомата входит в язык второго – мы решили 4-ю задачу.

    По поводу 2-й задачи – тут у меня нет строгого доказательства, но думаю, что если полученный автомат имеет циклы – то порождаемый язык имеет бесконечную мощность, в противном случае – конечную мощность. Породить все строчки можно обходом автомата (как обход графа, только еще выписывать буквы). Решение первой задачи вытекает из решения 3.1

    Это все теория. На приктике, то что сейчас называется “регулярными выражениями” — это расширение регулярных выражений в смысле способа задания регулярных языков (назовем это perl-style regexp). Даже проверка строки на соответсвие perl-style regexp – NP-полная задача, то есть решить вышеуказанные задачи для perl-style regexp будет сложно (доказательств нет, мне так кажется). Однако, на прктике, используются в основном не все богатсво perl-style regexp а подмножество, которое сводится к регулрным выражениям в математическом смысле. То есть можно определить множество регекспов, которые сводятся к автоматам, и решать задачи для них, а для сложных регекспов с back-reference, capture groups и пр решать вручную/приближенно/etc.

  • http://ivan.begtin.name ivbeg

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

    Вы совершенно правы что правила регекспов обычно используются не все и в некоторых случаях можно их сократить то некой конечной выборки.
    Мой подход заключается в построении шаблонов правил для классификации регулярных выражений и оценка «решабельности» задач в соответствии с этими правилами.
    Но универсального решения, увы, нет и встречать пока не доводилось.