TRANSDUCED-INPUT AUTOMATA WITH TRANSLUCENT LETTERS

Abstract

Finite automata with translucent letters 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 not 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 paper 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. We prove that all the three mentioned languages are accepted by the deterministic variant of the new model.