Information Technology Reference
In-Depth Information
immediately follows it in length. Then, transduction is iterated, because the result
of the translation (when it reaches the final state, on the bottom) is given as input of
another translation. The strings obtained in this way, when it reaches the final state,
are those of the tri-somatic language.
Fig. 4.1
An iterated transducer performing a tri-somatic growth
Figure 4.2 represents a transducer which realizes the translation of RNA tran-
scripts, according to the genetic code. This transducer has 21 states, which is ex-
actly the number of data encoded by the genetic code (20 aminoacids + the stop
character). In Fig. 4.2, the region constituted by the full circle in the center, together
with the bold line and the bold external circle, represents the initial state of the trans-
ducer. The states having transition to the external circle are the final states (where the
transducer is after reading three consecutive nucleotides). All the transitions from
non-final states translate the symbol into the empty character (indicated in the figure
with “-”). There are 25 transitions to 16 final states. In fact, in four cases there are
two different transitions providing the same output (R, L, S , and stop). Therefore,
the transducer translates all the 64 codons into 21 outputs (20 aminoacids and stop).
Apart from one case, all the final states have one or two transitions reaching again
the initial state. This means that the transitions cover in an almost uniform way all
the possible outputs. In principle, 5 transitions for each group of 4 final states, plus
an additional transition, for example, a schema of transitions 5+5+5+6 could encode
the 20 amino acids plus the stop character.
In the transducer of Fig. 4.2, the schema of final transitions 5+5+7+8 is near to the
minimal schema, apart from the redundancy of the 4 extra transitions (related to R,
L, S, and stop). We remark that a code of length 3 over an alphabet of four symbols,
where the third symbol is always significant, has to encode al least 20 elements.
In fact, the 4 groups of final states (each for each alphabet symbol) cannot have
only 4 transitions, otherwise the translation can be done only with strings of length
2. Therefore, at least 5 transitions for each group provide at least 20 transitions. It
