4
$\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 pushdown transduction iff it is a limited transduction function of some pushdown transducer.

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

Is the set of pushdown transductions closed under composition?

I know, how to prove that composition of a pushdown transduction and a regular transduction is a pushdown transduction, and that composition of a regular transduction and a regular transduction is a regular transduction, by explicitly constructing corresponding automata. But attempting to do this for two irregular pushdown transductions in the same straightforward way we get a transducer with two stacks (which is equivalent to Turing machine), which gives us nothing we have not known before…

$\endgroup$
1
  • $\begingroup$ Hard to digest this lengthy definition, but if I read this as a pushdown automaton having both input and output tape, closure under composition is highly improbable as the composition of two PD transducers can check whether the input string is in the intersection of two context-free languages. $\endgroup$ May 28 '21 at 4:54

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.