Transduced-Input Finite Automata with Translucent Letters

Finite automata with translucent letters are extensions of the usual finite state automata allowing to proceed the input not strictly left to right manner. There are some letters which are translucent for each internal state such that the automaton cannot read them. These are finite state devices that are able to accept a class of languages that is a superset of the regular languages, moreover, it contains some non-context-free languages. The class is closed under union, concatenation, however, it is not closed under intersection with regular sets. There are three linguistically important non context-free languages: the multiple agreement, the cross dependencies and the marked copy. These languages cannot be accepted by finite automata with translucent letters. In this thesis an extension of the model is presented in which the input is preprocessed by a finite state transducer. The transduced input is given to the finite automata with translucent letters, and it decides on acceptance. This is named as T-inputFAwtl i.e. Transduced-Input Finite Automata with Translucent Letters. We prove that all the three mentioned languages are accepted by the deterministic variant of the new model i.e. T-inputDFAwtl. Because of this we say that T-inputFAwtl has more expressive power than original finite automata with translucent letters. We also presented some closure properties of the class of languages accepted by non deterministic variant of this model i.e. T-inputNFAwtl. We proved that the language class accepted by that T inputNFAwtl is closed under union (if the same transducer is used), and it is closed under intersection with regular languages. Keywords: t-input automata, automata with translucent letters, Mealy automata, formal languages, finite state machines, transducers, finite state machines, closure properties