Constructions for alternating finite automata ∗
Abdelaziz Fellah, Helmut Jürgensen, Shyr-Shen Yu · International Journal of Computer Mathematics · 1990
Alternation is a natural generalization of nondeterminism. The model of alternating finite automata was first introduced and studied by Chandra et al. in [2]. Although alternating finite automata are no more powerful than deterministic finite automata with respect to language recognition, special features of alternating finite automata may provide new approaches and techniques for solving theoretical and practical problems concerning regular languages. In this paper we present direct constructions for the usual language theoretic operations in terms of alternating finite automata. Moreover, we discuss minimization and direct transformations between alternating, non-deterministic, and deterministic finite automata.