Consider the alphabet $\Sigma = \Sigma_c \cup \Sigma_i \cup \Sigma_r$ separated into call, internal, and return letters. Assume that $c \in \Sigma_c, r \in \Sigma_c$, and $a \in \Sigma_i$. I have a question regarding whether the language: $L = c^n a c^* a r^n$ is accepted by some Visibly Pushdown Automaton or not. $L$ is obviously context free, and the whole question is whether "not touching the stack" after reading a call symbol is allowed by some definititon of a VPA or not.

  • 1
    $\begingroup$ Do you mean $r \in \Sigma_r$? $\endgroup$
    – D.W.
    Mar 5 at 18:11


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.