КПК и регулярное выражение

Похоже, вы спрашиваете об этом: по заданному КПК M и регулярному выражению r создайте КПК, который принимает язык L(M), пересекающий L(r). Если это то, что вы хотите, ответ положительный, и конструкция утомительна, но понятна:

1. преобразовать регулярное выражение r в НКА N с помощью какой-либо конструкции, например, используемой в конструктивном доказательстве эквивалентности регулярных выражений и конечных автоматов
2. определить NFA N, чтобы получить DFA M ', используя некоторую конструкцию, например, конструкцию набора мощности (или подмножества) или любую другую, используемую в конструктивном доказательстве эквивалентности недетерминированных и детерминированных FA.
3. необязательно минимизировать M', чтобы получить M'', используя некоторый алгоритм минимизации DFA
4. now, construct the new PDA P as follows:
   • the states will be all ordered pairs (a, b) where a is a state in the PDA M and b is a state in the DFA M''
   • переходы будут из состояния (a, b) в (a', b') на символе s всякий раз, когда a переходит в a' на s в PDA M и b переходит в b' на s в DFA M'' (для эпсилон- переходы, перейти от (а, б) к (а', б)).
   • начальное состояние (ai, bi) будет состоять из начальных состояний ai и bi КПК М и ДКА М'' соответственно
   • состояниями приема будут те, в которых ОБА компонента принимают на своих соответствующих машинах (пары (a, b), где a принимает в PDA M, а b принимает в DFA M'')
   • стек обновляется по переходам только с КПК М

Сконструированная таким образом машина будет принимать все, что принимается PDA M и соответствует регулярному выражению r.