# Is pushdown transduction of a periodic sequence periodic?

Let’s define a pushdown transducer as a 9-tuple $$V = (A, B, S, Q_A, Q_S, \phi, \psi, \chi, q_0)$$, where $$A$$ is the finite input alphabet, $$B$$ is the finite output alphabet, $$S$$ is the finite stack alphabet, $$Q_A$$ are the finite set of read-from-input states, $$Q_S$$ is the finite set of read-from-stack states, $$\phi: (Q_A \times A) \cup (Q_S \times (S \cup \{ \epsilon \})) \to (Q_A \cup Q_S)$$ (where $$\epsilon \not\in S$$) - is the state transition function, $$\psi: (Q_A \times A) \cup (Q_S \times (S \cup \{ \epsilon \})) \to S^*$$ (where $$\epsilon \not\in S$$) is stack transition function, $$\chi: (Q_A \times A) \cup (Q_S \times (S \cup \{ \epsilon \})) \to B^*$$ (where $$\epsilon \not\in S$$) is output function, $$q_0 \in Q_A$$ is the initial state. Now, let’s define the total transducer function of $$V$$ of $$V$$ as $$f_V: A^* \to (Q_A \cup Q_S) \cup S^* \to B^*$$ defined by recurrence relation

$$f_V(\Lambda, q, \sigma) = \Lambda$$

$$f_V(a\alpha, q, \Lambda) = \begin{cases} \chi(q, a) f_V(\alpha, \phi(q, a), \psi(q, a)) & \quad q \in Q_A \\ \chi(q, \epsilon) f_V(\alpha, \phi(q, \epsilon), \psi(q, \epsilon)) & \quad q \in Q_S \end{cases}$$

$$f_V(a\alpha, q, \sigma s) = \begin{cases} \chi(q, a) f_V(\alpha, \phi(q, a), \sigma s \psi(q, a)) & \quad q \in Q_A \\ \chi(q, s) f_V(\alpha, \phi(q, s), \sigma \psi(q, s)) & \quad q \in Q_S \end{cases}$$

and limited transduction function as $$t_V(A^*) = f_V(A^*, q_0, \Lambda)$$.

We call a deterministic function $$A^* \to B^*$$ a finitary pushdown transduction iff it is a limited transduction function of some pushdown transducer.

We call a deterministic function $$f:A^{\infty} \to B^{\infty}$$ an infinitary pushdown transduction iff there exists some finitary pushdown transduction $$g: A^* \to B^*$$ such that $$\forall \alpha \in A^*, \beta \in A^\infty$$ we have $$f(\alpha \beta) = g(\alpha)f(\beta)$$.

Pushdown transducers are a more powerful computation model than finite state transducers, but less powerful than Turing machines.

Now, let's say that a sequence $$\alpha = a_0 a_1 a_2 ... \in A^\infty$$ is ultimately periodic iff $$\exists t, k \in \mathbb{N}$$ such that $$\forall n > t$$ we have $$a_{n + k} = a_n$$.

Now, suppose $$\alpha \in A^\infty$$ is an ultimately periodic sequence and $$f: A^\infty \to B^\infty$$ is an infinitary pushdown transduction. Is $$f(\alpha)$$ also periodic?

If $$f$$ is a regular transduction, then periodicity of $$f(\alpha)$$ is an easy consequence of pigeonhole principle. However, that proof does not work for pushdown transductions due to the fact that the number of possible contents of the stack is infinite.

• Do you mean ultimately periodic instead of periodic sequence? Jan 7 '21 at 5:46
• @J.-E.Pin, yes. However, in the textbook from which I got my first acquaintance with DFAs they were called just periodic. To avoid further confusion, I added the definition I was using to the body of the question. Jan 7 '21 at 10:38