Тестирование пересечения двух обычных языков - PullRequest
Новая
       10

Тестирование пересечения двух обычных языков

5 голосов
/ 26 февраля 2010

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

Язык указывается в виде строки типа glob, например

/foo/**/bar/*.baz

, где ** соответствует 0 или более символам, а * соответствует нулю или более символов, которые не /, а все остальные символы являются буквальными.

Есть идеи?

спасибо, микрофон

EDIT:

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

Ответы [ 2 ]

9 голосов
/ 26 февраля 2010

Создайте FA A и B для обоих языков и создайте "FA пересечения" AnB. Если AnB имеет хотя бы одно принимающее состояние, доступное из начального состояния, то есть слово на обоих языках.

Построение AnB может быть непростым делом, но я уверен, что есть учебники ФА, которые его освещают. Подход, который я выбрал бы:

  • Состояния AnB являются декартовым произведением состояний A и B соответственно. Состояние в AnB записывается (a, b), где a - это состояние в A, а b - в B.
  • Переход (a, b) ->r (c, d) (то есть переход с (a, b) на (c, d) для символа r) существует тогда и только тогда, когда a ->r c - это переход в A, а b ->r d - это переход B.
  • (a, b) - это начальное состояние в AnB, если a и b - это начальные состояния в A и B соответственно.
  • (a, b) является принимающим состоянием в AnB, если каждое является принимающим состоянием в соответствующей FA.

Это все с моей головы, и, следовательно, совершенно бездоказательно!

2 голосов
/ 26 февраля 2010

Я только что сделал быстрый поиск, и эта проблема разрешима (иначе можно сделать), но я не знаю ни одного хорошего алгоритма, чтобы сделать это. Одним из решений является:

  1. Преобразование обоих регулярных выражений в NFA A и B
  2. Создайте NFA, C, который представляет пересечение A и B.
  3. Теперь попробуйте каждую строку от 0 до количества состояний в C и посмотрите, принимает ли C ее (поскольку, если строка длиннее, она должна повторять состояния в одной точке).

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

...