3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do you mean ultimately periodic instead of periodic sequence? $\endgroup$
    – J.-E. Pin
    Jan 7 '21 at 5:46
  • $\begingroup$ @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. $\endgroup$ Jan 7 '21 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.