Вот эскиз подхода, который происходит со мной.Я думаю, что это должно работать, но это, вероятно, не лучший способ сделать это, поскольку он использует ужасно грязное преобразование из КПК в 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.Алгоритм для этого грязный и большой, но он работает.Как только вы это сделали, отметьте каждый символ терминала.Затем отметьте каждый символ, у которого есть правило, в котором есть только отмеченные символы с правой стороны, и повторяйте, пока вы не сможете пометить больше символов.Если вы можете отметить начальный символ, язык не пуст.В противном случае язык пуст.