Constructions for alternating finite automata^∗

^∗This work was supported by the natural sciences and engineering research council of canada, Grants OGP0000243 and OGP0041630.

Abstract

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.

Keywords:

• Alternating Finite Automata
• Finite Automata
• Alternation
• Nondeterminism
• NFA with Nondeterministic Starting State

C.R. Categories:

• F.1.1
• F.1.2

^∗This work was supported by the natural sciences and engineering research council of canada, Grants OGP0000243 and OGP0041630.

^†On leave from Kent State University, Kent, Ohio, USA.

^∗This work was supported by the natural sciences and engineering research council of canada, Grants OGP0000243 and OGP0041630.

^†On leave from Kent State University, Kent, Ohio, USA.

Notes

^∗This work was supported by the natural sciences and engineering research council of canada, Grants OGP0000243 and OGP0041630.

^†On leave from Kent State University, Kent, Ohio, USA.