Exercise 16:

Regular description for σ(L)\sigma(L) where L={w{a,b}wa2˙}L=\{ w \in \{a,b\}^* \mid |w|_a\in\dot{2} \}
and σ\sigma is the transducer with states {0,1,2}\{0,1,2\}, initial state 00, and transitions
0aaba1,  0bbb2,  1ab2,  1ba0,  2aa1,  2bbbba00\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{a,b}wa2˙}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:
0aaba10bbb21ab21ba02aa12bbbba0\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 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 or w2w'2 (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 abbaLabba\in L and the following execution: Since there is no more input, the execution terminates. Hence, the image of the word abbaLabba\in L through the transducer is abaabbaabaabba.
Authors: Guillem Godoy / Documentation:
To be able to submit you need to either log in, register, or become a guest.