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.

There are numerous connections between the theory of formal languages and that of symbolic dynamics. In each, the transition from one dimension to two dimensionsis accompanied by much difficulty due in large part to the emptiness problem, which is related to the presence (or lack thereof) of periodic points and is known to be undecidable. Here, we focus on two-dimensional languages that have the property that all blocks allowed by the language can be extended to a configuration of the plane satisfying the structure of the language; for such languages the emptiness problem is not an issue. We first show that dot systems may be associated with two-dimensional languages having this property, so that we might employ these languages as varied examples. We next define a new type of finite automaton and with it, a tool for recognizing two-dimensional "strings" of data. It is then shown that these automata correctly represent the sofic shift spaces that result from the application of block maps to shifts of finite type. Thereafter, these automataare utilized to investigate properties of transitivity in the two-dimensional languages that they represent. More specifically, new definitions for different types of two-dimensional transitivity are adapted from topological dynamics and then illustrated through the use of dot systems. The appearance of periodic points in the languages represented by these automata is also explored, with a main result being that the existence of a periodic pointis guaranteed under certain conditions. Finally, issues of equivalence are introduced in the two-dimensional setting with regards to formal languages (syntactic monoids) and symbolic dynamics (the follower sets of a graph representing a sofic shift space).