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

Question

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

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

Язык указан подобной шарику строкой как

/foo/**/bar/*.baz

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

Какие-либо идеи?

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

Править:

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

5

parsing finite-automata automata

задан Mike Samuel 16 August 2011 в 20:44

2 ответа

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

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

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

2

ответ дан 13 December 2019 в 19:25

Другие вопросы по тегам:

parsing finite-automata automata

Похожие вопросы:

score 9 · Accepted Answer

Постройте 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 -> rc является переходом в A , и b -> rd - переход в B .
(a, b) - это начальное состояние в AnB , если и только если a и b - начальные состояния в A и B соответственно.
(a, b) является состоянием приема в AnB , если каждое из них является состоянием приема в соответствующей FA.

Это все не в моей голове и, следовательно, полностью недоказано!