1
$\begingroup$

Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such words over alphabet $\Sigma$, for which there exists some run of automata $A$, such as in every step symbols on the stack belongs to the regular language $R$.

Show that language $L_R(A)$ is context-free.

Improve this question
$\endgroup$
1
  • $\begingroup$ I would try to solve this using a sort-of product construction between $A$ and $R$. I'm not sure if it will suffices, but it's worth a try, I think. (Also, you should show some effort by posting your attempt.) $\endgroup$
    – chi
    Jun 15, 2018 at 10:20

1 Answer 1

Reset to default
3
$\begingroup$

Let $Q$ be the set of states in a DFA $D$ for $R$. We replace $\Gamma$ with $\Gamma \times Q$, and update the PDA so that the stack contains, apart from the original stack symbols, also the state that $D$ is in after reading the current word on the stack. The PDA only allows transitions if the element at the top of the stack corresponds to an accepting state of $D$, and also checks this condition at the very end.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.