Exercise 17:

Regular description for σ(L)\sigma(L) where L={xay{a,b}y=1}L=\{ xay \in \{a,b\}^* \mid |y|=1 \}
and σ\sigma is the transducer with states {0,1}\{0,1\}, initial state 00, and transitions
0aaba0,  0bb1,  1ab0,  1baa10\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{a,b}y=1}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:
0aaba00bb11ab01baa1\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 wLw\in L we would start the execution with the word 0w0w and proceed until obtaining a word of the form w0w'0 or w1w'1 (i.e., a word that cannot be rewritten any further), where ww' would be the generated output.

In order to get more intuition on how this transducer works, consider the word bbaaLbbaa\in L and the following execution: Since there is no more input, the execution terminates. Hence, the image of the word bbaaLbbaa\in L through the transducer is baabababaababa.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.