## Exercise ‹17›:

Regular description for $\sigma(L)$ where $L=\{ xay \in \{a,b\}^* \mid |y|=1 \}$
and $\sigma$ is the transducer with states $\{0,1\}$, initial state $0$, and transitions
$0\xrightarrow{a\,|\,aba}0,\;0\xrightarrow{b\,|\,b}1,\;1\xrightarrow{a\,|\,b}0,\;1\xrightarrow{b\,|\,aa}1$
Give a regular description for the image of the language $L=\{ xay \in \{a,b\}^* \mid |y|=1 \}$ through the transducer represented here. Such transducer can be alternatively formalized as the following set of rewrite rules:
$\begin{array}{l} 0a\to aba0\\ 0b\to b1\\ 1a\to b0\\ 1b\to aa1\end{array}$
In this alternative setting, to rewrite a word $w\in L$ we would start the execution with the word $0w$ and proceed until obtaining a word of the form $w'0$ or $w'1$ (i.e., a word that cannot be rewritten any further), where $w'$ would be the generated output.

In order to get more intuition on how this transducer works, consider the word $bbaa\in L$ and the following execution:
• $0~~bbaa$
Initially, the transducer is at state $0$ and it remains to read the whole word $bbaa$. Moreover, no output has been produced yet.
• $b~~1~~baa$
By reading a $b$ from state $0$, the transducer has moved to state $1$ and outputted $b$. (Equivalently, the 2nd rewrite rule has been applied.)
• $b~aa~~1~~aa$
By reading a $b$ from state $1$, the transducer has moved to state $1$ and outputted $aa$. (Equivalently, the 4th rewrite rule has been applied.)
• $b~aa~b~~0~~a$
By reading an $a$ from state $1$, the transducer has moved to state $0$ and outputted $b$. (Equivalently, the 3rd rewrite rule has been applied.)
• $b~aa~b~aba~~0$
By reading an $a$ from state $0$, the transducer has moved to state $0$ and outputted $aba$. (Equivalently, the 1st rewrite rule has been applied.)
Since there is no more input, the execution terminates. Hence, the image of the word $bbaa\in L$ through the transducer is $baababa$.
Authors: Guillem Godoy / Documentation:
 main { // Write here your regular description... } To be able to submit you need to either log in, register, or become a guest.