# Is the language accepted by a DFA with a fixed word on the stack after consuming it a deterministic context free language?

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.

• Yes, sorry about that. I have already deleted the question from TCS stack exchange. Jan 5 at 3:56

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$$.)

• 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. Jan 5 at 6:12
• @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!
– D.W.
Jan 5 at 7:16
• 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. Jan 6 at 19:50
• 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.) Jan 6 at 19:51
• @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. Jan 7 at 23:01