Automata That May Change Their Mind
Markus Holzer, Martin Kutrib · Journal of automata, languages and combinatorics · 2020
We introduce the concept of mind-changing automata. Basically, the idea is that at the outset the automaton is partially deterministic. Whenever the automaton encounters a situation for which it has an undefined transition, it may choose an appropriate transition out of a set of available transitions. The chosen transition is then added to the transition function. Finally, whenever the automaton is in a situation for which a transition is defined, it can change its mind and interchange the transition by an alternative transition from the set of available transitions. So, the number of transition changes is a natural parameter of the devices considered. We show that mind-changing finite automata (MCFAs) only accept regular languages. Moreover, we prove that, from a descriptional complexity point of view, a single mind-change is already better than nondeterminism, that is, there is a sequence of regular languages $(L_n)_{n\geq 3}$ accepted by $n$-state complete MCFA with a single alternative transition with at most one mind-change such that any nondeterministic finite automaton accepting $L_n$ requires at least $n+\log n-1$ states. Moreover, we perform a basic study on computational complexity issues for MCFAs with transition changes limited to a single state. We also consider mind-changing pushdown automata proving that the families of languages induced by the number of mind-changes lie strictly in between the deterministic context-free and context-free language families and form a proper mind-change hierarchy. What concerns the descriptional complexity of these level, it can be shown that there are non-recursive trade-offs between the hierarchy levels of mind-changing pushdown automata, that is, the change in description size cannot be bounded by any recursive function.