1971/10/01 by Frank R. Moore · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Machine Learning and Algorithms #Computability, Logic, AI Algorithms #Mathematical proof #Nondeterministic algorithm #Deterministic finite automaton #Nondeterministic finite automaton #Finite-state machine #Equivalence (formal languages) #Quantum finite automata #Discrete mathematics #Automaton #DFA minimization #Deterministic automaton #Mathematics #Finite set #Finite state #Set (abstract data type) #Automata theory #Computer science #Theoretical computer science #Algorithm
paper · doi:10.1109/t-c.1971.223108
openalex publication_date 1971/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
The bounds on state-set size in the proofs of the equivalence between nondeterministic and deterministic finite automata and between two-way and one-way deterministic finite automata are considered. It is shown that the number of states in the subset machine in the first construction cannot be reduced for certain cases. It is also shown that the number of states in the one-way automation constructed in the second proof may be reduced only slightly.