Theory of Atomata

Details Theory of Atomata Theory of Atomata

2011-02-18

arxiv.org/abs/1102.3901v1

Computer Science

Formal Languages and Automata Theory

12 pages, 2 figures

Scientific paper

We show that every regular language defines a unique nondeterministic finite automaton (NFA), which we call "atomaton", whose states are the "atoms" of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of the language. We describe methods of constructing the atomaton, and prove that it is isomorphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study "atomic" NFA's in which the right language of every state is a union of atoms. We generalize Brzozowski's double-reversal method for minimizing a deterministic finite automaton (DFA), showing that the result of applying the subset construction to an NFA is a minimal DFA if and only if the reverse of the NFA is atomic.

Affiliated with

Also associated with

No associations

Rating

Theory of Atomata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Theory of Atomata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theory of Atomata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-158960