Существует ли алгоритм, который может определить, соответствует ли один обычный язык какому-либо входу другому регулярному языку? - PullRequest
Новая
       8

Существует ли алгоритм, который может определить, соответствует ли один обычный язык какому-либо входу другому регулярному языку?

17 голосов
/ 02 сентября 2010

Допустим, у нас есть регулярные выражения:

  • Привет W. * rld
  • Hello World
  • . * Мир
  • . * З. *

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

Для этого мне нужно выяснить, соответствует ли одно регулярное выражение какому-либо входу, совпадающему с другим выражением. Это возможно?

Billy3

Ответы [ 4 ]

11 голосов
/ 02 сентября 2010

Любое регулярное выражение может быть связано с DFA - вы можете минимизировать DFA и, поскольку минимальная форма уникальна, вы можете решить, эквивалентны ли два выражения. Дани Крико указал на алгоритм Хопкрофта O (n log n). Существует еще один улучшенный алгоритм Хопкрофта и Крафта, который проверяет эквивалентность двух DFA в O (n).

Для хорошего обзора по этому вопросу и интересного подхода к этому я рекомендую статью Проверка эквивалентности регулярных языков , из arXiv.

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

2 голосов
/ 02 сентября 2010

Конечно !.Регулярное выражение может быть представлено как FSM (конечный автомат), и существует технически бесконечное количество FSM, которые могут распознавать одну и ту же строку.

Изоморфизм - это имя, которое описывает, эквивалентны ли два FSM.Есть пара алгоритмов, чтобы минимизировать FSM.Например, алгоритм минимизации Хопкрофта может минимизировать два FSM в O (n log n) на автомате n состояний.

2 голосов
/ 02 сентября 2010

Да.

Проблема эквивалентности двух обычных языков решаема.

Схема алгоритма:

  • свести к минимуму оба DFA
  • проверьте, изоморфны ли они
0 голосов
/ 30 ноября 2015

Эта проблема называется «включением» или «подчинением» регулярных выражений, потому что вы запрашиваете, включает ли набор слов, сопоставленный одному регулярному выражению, (или включает в себя) набор слов, сопоставленных другим регулярным выражением. Равенство - это другой вопрос, который обычно означает, совпадают ли два регулярных выражения с одинаковыми словами, т. Е. Что они функционально эквивалентны. Например, «а *» включает в себя «аа *», в то время как они не равны.

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

Ввод r1 и r2 Выведите Да, если r1 включает в себя r2

  1. Создание DFA (r1) и DFA (r2)
  2. Создать Neg (DFA (r1)) (что в точности совпадает с теми словами, которые не соответствуют r1)
  3. Создать Neg (DFA (r1)) x DFA (r2) (что в точности совпадает с теми словами, которые соответствуют Neg (DFA (r1)) и DFA (r2))
  4. Убедитесь, что автомат, созданный в 3., не соответствует ни одному слову

Это работает, поскольку вы проверяете, что нет слов, соответствующих r2, которые не соответствуют r1.

...