Звучит так, будто вы спрашиваете следующее: учитывая КПК М и регулярное выражение r, создайте КПК, который принимает язык L (M), пересекающийся с L (r).Если это то, что вам нужно, ответ - да, а конструкция утомительна, но прямолинейна:
- преобразуйте регулярное выражение r в NFA N, используя некоторую конструкцию, например, используемую в конструктивном доказательстве.эквивалентности регулярных выражений и конечных автоматов
- определяют NFA N для получения DFA M ', используя некоторую конструкцию, например конструкцию powerset (или подмножество), или любую, используемую в конструктивном доказательстве эквивалентностинедетерминированные и детерминированные FA
- опционально, минимизируйте M ', чтобы получить M' ', используя некоторый алгоритм минимизации DFA
- сейчас, сконструируйте новый PDA P следующим образом:
- состояниябудут все упорядоченные пары (a, b), где a - это состояние в КПК M, а b - это состояние в DFA M ''
- , переходы будут из состояния (a, b) в (a', b') для символа s всякий раз, когда переходы к a 'on s в КПК M и b переходы к b' on s в DFA M '' (для эпсилон-переходов переходите от (a, b) к (a ',б)).
- ИнициативаВсе состояния (ai, bi) будут состоять из начальных состояний ai и bi PDA M и DFA M '', соответственно
- принимающие состояния будут те, в которых оба компонента принимают в своих соответствующих машинах (пары (a, b), где a принимает в КПК M, а b принимает в DFA M '')
- стек обновляется в соответствии с переходами только из КПК M
Машина, сконструированная таким образом, будет принимать все, что принимается КПК М и соответствует регулярному выражению r.