## Exercise ‹16›:

Regular description for $\sigma(L)$ where $L=\{ w \in \{a,b\}^* \mid |w|_a\in\dot{2} \}$
and $\sigma$ is the transducer with states $\{0,1,2\}$, initial state $0$, and transitions
$0\xrightarrow{a\,|\,aba}1,\;0\xrightarrow{b\,|\,bb}2,\;1\xrightarrow{a\,|\,b}2,\;1\xrightarrow{b\,|\,a}0,\;2\xrightarrow{a\,|\,a}1,\;2\xrightarrow{b\,|\,bbba}0$
Give a regular description for the image of the language $L=\{ w \in \{a,b\}^* \mid |w|_a\in\dot{2}\}$ through the transducer represented here. Such transducer can be alternatively formalized as the following set of rewrite rules:
$\begin{array}{l} 0a\to aba1\\ 0b\to bb2\\ 1a\to b2\\ 1b\to a0\\ 2a\to a1\\ 2b\to bbba0\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$ or $w'2$ (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 $abba\in L$ and the following execution:
• $0~~abba$
Initially, the transducer is at state $0$ and it remains to read the whole word $abba$. Moreover, no output has been produced yet.
• $aba~~1~~bba$
By reading an $a$ from state $0$, the transducer has moved to state $1$ and outputted $aba$. (Equivalently, the 1st rewrite rule has been applied.)
• $aba~a~~0~~ba$
By reading a $b$ from state $1$, the transducer has moved to state $0$ and outputted an $a$. (Equivalently, the 4th rewrite rule has been applied.)
• $aba~a~bb~~2~~a$
By reading a $b$ from state $0$, the transducer has moved to state $2$ and outputted $bb$. (Equivalently, the 2nd rewrite rule has been applied.)
• $aba~a~bb~a~~1$
By reading an $a$ from state $2$, the transducer has moved to state $1$ and outputted an $a$. (Equivalently, the 5th rewrite rule has been applied.)
Since there is no more input, the execution terminates. Hence, the image of the word $abba\in L$ through the transducer is $abaabba$.
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.