# Accession Number:

## AD0719398

# Title:

## An N Log N Algorithm for Minimizing States in a Finite Automaton,

# Descriptive Note:

# Corporate Author:

## STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1971-01-01

# Pagination or Media Count:

## 15.0

# Abstract:

An algorithm is given for minimizing the number of states in a finite automaton or for determining if two automata are equivalent. The asymptotic running time of the algorithm is bounded by k n log n where k is some constant and n is the number of states. The constant k depends linearly on the size of the input alphabet. Author

# Descriptors:

# Subject Categories:

- Computer Programming and Software
- Computer Hardware