2
$\begingroup$

Let $\cal M$ be a deterministic stack automaton ${\cal M } = (Q, \Sigma, \Gamma, \delta, q_0, F, Z_0 )$. Let $\gamma \in \Gamma^* $ a word on the stack alphabet. Is it true that the language $$L = \{ w \in \Sigma^* \mid (q_0,w,Z_0) \vdash^* (q,\epsilon, \gamma),\ q \in F \}$$ is a deterministic context free language? Is this family different from the family of deterministic context free languages? If so, how is this family of languages called in the literature? I was particullary interested in the case of $\gamma = Z_0$.

Commentary: This question was migrated from TCS stack exchange.

$\endgroup$
1
  • $\begingroup$ Yes, sorry about that. I have already deleted the question from TCS stack exchange. $\endgroup$
    – hedphelym
    Jan 5 at 3:56

1 Answer 1

2
$\begingroup$

Yes, $L$ is a deterministic context-free language.

I will describe how to build a deterministic pushdown automaton $\mathcal{M}'$ to recognize $L$. The stack alphabet of $\mathcal{M}'$ is $\Gamma' = \Gamma \times \{0,1,\dots,|\gamma|,\bot\}$. When the stack of $\mathcal{M}$ contains the word $\beta=(\beta_1,\beta_2,\dots,\beta_k)$, the stack of $\mathcal{M}'$ contains the word

$$\beta'=((\beta_1,m_1),(\beta_1,m_2),\dots,(\beta_k,m_k)),$$

where $m_i=i$ if $i \le |\gamma|$ and $(\gamma_1,\dots,\gamma_i)=(\beta_1,\dots,\beta_i)$, or $m_i=\bot$ otherwise. Also, the states $Q'$ of $\mathcal{M}'$ are given by $Q'=Q \times \{0,1\}$. When $\mathcal{M}$ is in state $q$, $\mathcal{M}'$ is in state $(q,1)$ if the top of $\mathcal{M}'s$ stack is of the form $(\cdot,|\gamma|)$, or in state $(q,0)$ otherwise. The accepting states of $\mathcal{M'}$ are $F'=\{(q,1) \mid q \in F\}$. You should be able to figure out how to adjust the transitions to ensure that $\mathcal{M}'$ behaves as described.

Then $\mathcal{M}'$ accepts exactly $L$, and is deterministic. I'll let you fill in the details of the proof.

You can generalize this to allow any $\gamma$ such that $\gamma \in R$, where $R$ is a regular language. (We modify the proof above by replacing $\{0,1,\dots,|\gamma|,\bot\}$ with the states of a DFA recognizing $R$.)

$\endgroup$
5
  • $\begingroup$ Thanks a lot for the fast and detailed answer. I think I have a construction such that we need to add $|\gamma|$ states and modify the transition function accordingly. Also, is it true that this family of languages is strictly contained in the family of deterministic context-free languages? I thought of a counterexample, but I'm not sure. $\endgroup$
    – hedphelym
    Jan 5 at 6:12
  • 1
    $\begingroup$ @lenareole, I think yes, it is a deterministic context-free - if you work through the construction I believe all of the transition function of $\mathcal{M}'$ will remain deterministic. But please check my reasoning carefully, I might well have made some mistake. If you have a construction that avoids the need to blow up the stack alphabet, that's very nifty! $\endgroup$
    – D.W.
    Jan 5 at 7:16
  • 1
    $\begingroup$ The final remark (suggesting acceptance using a regular string on the stack) is very elegant. This reminds us that the set of (all) stacks that occur during a PDA computation is itself regular. $\endgroup$ Jan 6 at 19:50
  • 2
    $\begingroup$ Alternatively (I think) the bottom $|\gamma|$ symbols of the pushdown can be kept in the finite state memory of the machine. (Moving the explosion from stack symbols to states.) $\endgroup$ Jan 6 at 19:51
  • $\begingroup$ @D. W. My nifty construction turned out to be erroneous as I thought it was but couldn't understand why. I think I was able to construct a deterministic pusdown automata that accepts the language of words accepted with $\gamma$ as a prefix, which is less difficult to do. $\endgroup$
    – hedphelym
    Jan 7 at 23:01

Your Answer

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

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