(2) Creare a finite state transducer that implements the following
    conversions:

     aaa => zzz
     aab => zzb
     baa => bzz
     aba => zbz
     bbb => bbb
     bba => bbz
     bab => bzb

    Display the transducer as a graph. Comment on its complexity.

solution: 

From the conversions given we can see:
1. a gets converted to z
2. b remains as b
3. abb conversion does not exist out of the possible 8 variations.

Mealy machine extension to a simple FSA is defined as FST - finite
state transducer. FST is discussed as a generator.

Based on the notations used in the text-book,

Q = a finite set of N states. for our problem, it is three.
E = finite alphabet of complex symbols - feasible pairs
E = { a:Z, b:b } or  { a:Z, b } b:b is the default pair
q0 is the start state

F: the set of final states F C Q

        a:z, b         a:z       a:z, b
-> q0 ----------> q1 -------> q2 --------> q3
   |                          |
   |    b               b     |
   ------------>  q4 ---------


If complexity is defined in terms of number of paths that can be taken
at a node then the complexity is 2 at start and 1 elsewhere. So
overall complexity for the FST conversion is 2.

time-complexity [1] of transforming a string using a deterministic FST
depends only on the length of the tring and it is lienar with respect
to this length.  So, time-complexity is 3.

search space complexity [2] ?? no idea how to comopute this.


reference 

1: S. Lucas, "Evolving finite state transducers: some initial
explorations".

2: T. Hazen, I. Hetherington, H. Shu, and K. Livescu, "Pronunciation modeling using a finite state transducer representation".