This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
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: