Non-returning deterministic and nondeterministic finite automata with translucent letters

¹ Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 25 Prague 1, Czech Republic
² Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany

^* Corresponding author: f.otto@uni-kassel.de

Received: 28 January 2023
Accepted: 19 September 2023

Abstract

Here, we propose a variant of the nondeterministic finite automaton with translucent letters (NFAwtl), which, after reading and deleting a letter, does not return to the left end of its tape, but instead continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, reject, or continue, which means that it reads the remaining tape contents again from the beginning. This type of automaton, called a non-returning finite automaton with translucent letters or an nrNFAwtl, is strictly more expressive than the NFAwtl. We study the expressive capacity of this type of automaton and that of its deterministic variant, comparing them to various other types of finite automata that do not simply read their input from left to right. Also, we are interested in the closure properties of the resulting classes of languages and in the complexity of the fixed membership problem.