202503170203

Tags : Weighted Automata and Transducers

Image of a Regular Language under a Sequential Transducer is Regular

---

Theorem

Consider a regular language $L\subseteq A^{\ast }$ and a Sequential Transducers $f:A^{\ast }\to B^{\ast }$, then the language which is the image $L^{\prime }=f(L)\subseteq B^{\ast }$.

Let $L$ be a regular language and $\mathcal{A}=(Q_{\mathcal{A}},q_0,F_{\mathcal{A}},{\delta }_{\mathcal{A}})$ be a deterministic automaton for this and let $f=(Q_f,A,B,q_0,m_0,\varphi ,{\delta }_f,\rho )$ be a sequential transducer. We now construct an automata for $f(L)$ in the following way:

• $Q=Q_{\mathcal{A}}\times Q_f\bigsqcup \{q_{\text{start}},q_{\text{fin}}\}$
• $q_0=q_{\text{start}}$
• $F=\{q_{\text{fin}}\}$
• The transition function is a bit more complicated and will be described in steps:
  • Given a state $(q,p)$ if we were to read an alphabet $a$, that would change states in the input automata and transducer, and our new automata gets to read the the output of the transition.
    • For each $a\in A,(q,p)\stackrel{\varphi (p,a)}{\to }({\delta }_{\mathcal{A}}(q,a),{\delta }_f(p,a))$
  • All string must start with $m_0$ and only then can the above computation can begin
    • $q_{start}\stackrel{m_0}{\to }(q_{(0,\mathcal{A})},q_{(0,f)})$
  • All words endings are decided by $\rho$ in the transducer and hence we have
    • $(\_,p)\stackrel{\rho (p)}{\to }{q}_{\text{fin}}$

This describes a non-deterministic automata who language is the image of $L$ under $f$, so we are done.

---

References