#### Title

#### Graduation Year

2008

#### Document Type

Thesis

#### Degree

M.A.

#### Degree Granting Department

Mathematics and Statistics

#### Major Professor

Natasha Jonoska, Ph.D.

#### Keywords

Sequences of words, Finite state automata with output, Entropy, Picture languages, Local languages

#### Abstract

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.

#### Scholar Commons Citation

Dolzhenko, Egor, "Transducer dynamics" (2008). *Graduate Theses and Dissertations.*

http://scholarcommons.usf.edu/etd/217