Finite Automata with Translucent Letters Applied in Natural and Formal Language Theory

Abstract

An important direction of computational and formal linguistics is to find good (mathematical and computational) models to describe linguistic phenomena. These models can also help to understand language acquisition, thinking and other mental activities. In this paper we consider finite automata with translucent letters. These models do not read their input strictly from left to right as traditional finite automata, but for each internal state of such a device, certain letters are translucent, that is, in this state the automaton cannot see them. We solve the parsing problem of these automata, both in the deterministic and in the nondeterministic cases. By introducing the permutation operator the class of regular languages is extended. It is shown that this extended class inside the class of languages that can be accepted by nondeterministic finite automata with translucent letters. Some interesting examples from the formal language theory and from a segment of the Hungarian language are shown presenting the applicability of finite automata with translucent letters both in formal and natural languages.