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

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

Язык определяется строкой в ​​виде глобуса, например

/foo/**/bar/*.baz

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

Есть идеи?

спасибо, майк

РЕДАКТИРОВАТЬ:

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


parsing finite-automata automata
person Mike Samuel    schedule 26.02.2010    source источник
comment
Какой язык вы будете использовать для выполнения проверки? Вероятно, вам понадобится написать тестовый стенд для этого. Если бы вы могли опубликовать довольно полный тестовый стенд, это помогло бы.   -  person Mark Byers    schedule 26.02.2010
comment
Это нужно будет запустить в JS. Конечно, мне придется написать тестовый стенд. Я нашел полезное подмножество, для которого я могу эффективно вычислить пересечение, проделывая некоторые трюки. Полезным является подмножество, в котором * и ** могут стоять только в начале или сразу после /, а / не может стоять рядом с другим /. Это означает, что мне никогда не нужно беспокоиться о том, может ли foo соответствовать boo*baz — мне приходится выполнять поиск с возвратом, но это не смешно, поскольку я всегда могу превратить текст, следующий за * или **, в суффикс. чек об оплате.   -  person Mike Samuel    schedule 02.03.2010

Ответы (2)


arrow_upward
10
arrow_downward

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

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

  • Состояния 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.

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

person Edmund    schedule 26.02.2010
comment
Что ж, это хорошо задокументированная конструкция, называемая декартовой машиной произведения, многие люди опередили вас в этом, и это хорошо задокументированный и правильный метод получения FA, распознающего пересечение языков, распознаваемых другими FA. Просто говорю. - person Patrick87; 17.08.2011

arrow_upward
2
arrow_downward

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

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

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

person Bishnu    schedule 26.02.2010