Give a regular description for the image of the language
L={w∈{a,b}∗∣∣w∣a∈2˙} through the transducer represented
here.
Such transducer can be alternatively formalized as
the following set of rewrite rules:
0a→aba10b→bb21a→b21b→a02a→a12b→bbba0
In this alternative setting, to rewrite a word
w∈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∈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∈L through the transducer is
abaabba.