Алгоритм пересечения регулярных выражений с cfg
Я ищу алгоритм, который выводит, если пересечение регулярного выражения и грамматики свободного контекста пусто или нет. Я знаю, что эта проблема разрешима, однако я не могу найти пример реализации (в псевдокоде).
Может ли кто-нибудь предоставить мне такой алгоритм, если возможно, в.NET, но это не обязательно. Эта проблема также называется "регулярным пересечением". Поиск в Google дает мне только геометрический алгоритм или теорию об этом.
редактировать:
Кто-нибудь. Я действительно застрял на нем и пока ничего не могу найти.
2 ответа
Вот набросок подхода, который происходит со мной. Я думаю, что это должно работать, но это, вероятно, не лучший способ сделать это, поскольку он использует ужасно грязное преобразование из КПК в CFG.
Преобразуйте регулярное выражение в недетерминированный конечный автомат (NFA) и сократите его до минимального детерминированного конечного автомата (DFA). Конвертируйте контекстно-свободную грамматику (CFG) в автоматную загрузку (PDA). Эти первые шаги - все хорошо известные и довольно простые алгоритмы.
Возьмите пересечение DFA и PDA, который также является PDA. Мы будем говорить, что DFA имеет состояния S1, начальное состояние s1, конечные состояния F1 и переходы delta1 в форме ((источник, триггер), пункт назначения), а PDA имеет состояния S2, начальное состояние s2, конечные состояния F2 и транзитные переходы. delta2 формы ((источник, триггер, поп), (пункт назначения, push)). Новый КПК имеет состояния S1 X S2, каждое состояние помечено парой. Он имеет конечные состояния F1 X F2 и начальное состояние (s1,s2). Теперь о переходах.
Для каждого перехода d элемент delta2, для каждого состояния s элемент s1 найдите переход t элемент delta1 вида ((s,d.trigger),?). Сделайте новый переход (((d.source, s), d.trigger, d.pop), ((d.destination, t.destination), d.push)).
Этот новый КПК должен принимать пересечение языков, созданных RE и CFG. Чтобы проверить, является ли язык пустым, вам необходимо преобразовать его обратно в CFG. Алгоритм для этого грязный и большой, но он работает. Как только вы это сделали, отметьте каждый символ терминала. Затем отметьте каждый символ, у которого есть правило, в котором есть только отмеченные символы с правой стороны, и повторяйте, пока вы не сможете пометить больше символов. Если вы можете отметить начальный символ, язык не пуст. В противном случае язык пуст.
На самом деле существует более простой алгоритм вычисления пересечения контекстно-свободной грамматики и регулярного выражения. Он не использует автоматы с выталкиванием вниз, получение которых из CFG с несколькими преобразованиями может быть дорогостоящим.
Это решение было представлено в:
Ю. Ба-Гилель, М. Прлес и Э. Шамир. 1965. О формальных свойствах грамматик простой структуры фраз. Z. Фонетика, Sprachwissen. Комм. 15 (1961), 143-172. Ю. Бар-Хиллель, Язык и информация, Аддисон-Уэсли, Рединг, Массачусетс (1965), 116–150.
но вы можете найти более простую версию в:
Ричард Бейгель и Уильям Гасарч. .. Доказательство того, что пересечение контекстно-свободного языка и обычного языка является контекстно-свободным, не использующим автоматы выталкивания вниз. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf (.).
Если это поможет, это решение было реализовано в Pyformlang (https://pyformlang.readthedocs.io/), и вы можете найти его на Github для Python (https://github.com/Aunsiels/pyformlang/blob/master/pyformlang ). /cfg/cfg.py)