Transducer dynamics

Transducers are finite state automata with an output. In this thesis, we attempt to classify sequences that can be constructed by iteratively applying a transducer to a given word. We begin exploring this problem by considering sequences of words that can be produced by iterative application of a transducer to a given input word, i.e., identifying sequences of words of the form w, t(w), t²(w), . . . We call such sequences transducer recognizable. Also we introduce the notion of "recognition of a sequence in context", which captures the possibility of concatenating prefix and suffix words to each word in the sequence, so a given sequence of words becomes transducer recognizable. It turns out that all finite and periodic sequences of words of equal length are transducer recognizable. We also show how to construct a deterministic transducer with the least number of states recognizing a given sequence. To each transducer t we associate a two-dimensional language L²(t) consisting of blocks of symbols in the following way. The first row, w, of each block is in the input language of t, the second row is a word that t outputs on input w. Inductively, every subsequent row is a word outputted by the transducer when its preceding row is read as an input. We show a relationship of the entropy values of these two-dimensional languages to the entropy values of the one-dimensional languages that appear as input languages for finite state transducers.

Grantor dc:publisher

Digital Commons @ University of South Florida

Year dc:date

2007

Author dc:creator

• Dolzhenko, Egor

• Sequences of Words
• Finite State Automata with Output
• Entropy
• Picture Languages
• Local Languages
• American Studies
• Arts and Humanities

Statement dc:rights

• default

Repository record dc:identifier

https://digitalcommons.usf.edu/etd/217

OAI identifier oai:identifier

oai:digitalcommons.usf.edu:etd-1216