ON PROPER LANGUAGES AND TRANSFORMATIONS OF LEXICALIZED TYPES OF AUTOMATA

Motivated by the way in which sentences of natural languages are analyzed in linguistics, types of automata are studied that work on extended alphabets which, in addition to the input symbols, also contain certain auxiliary symbols. The latter model the use of (morphological, syntactical, and semantical) categories in the process of analyzing sentences. The automata we consider work on so-called characteristic languages, that is, on languages that include auxiliary symbols. The proper language is obtained from a characteristic language by removing all occurrences of auxiliary symbols. By requiring that the automata are lexicalized, we restrict the lengths of blocks of auxiliary symbols that are admitted. We study the classes of proper languages for deterministic finite-state acceptors, pushdown automata, two-pushdown automata, and freely rewriting restarting automata that are lexicalized. In addition, we use a generalization of the notion of proper language to associate a (binary) transformation with a characteristic language. This leads to the study of transformations of a certain form for the above types of automata.