# A maxmin problem on finite automata

- Authors
- Journal
- Discrete Applied Mathematics 0166-218X
- Publisher
- Elsevier
- Publication Date
- Volume
- 23
- Issue
- 1
- Identifiers
- DOI: 10.1016/0166-218x(89)90037-1

## Abstract

Abstract We solve the following problem proposed by Straubing. Given a two-letter alphabet A, what is the maximal number of states f( n) of the minimal automaton of a subset of A n , the set of all words of length n. We give an explicit formula to compute f( n) and we show that 1= lim inf n→∞nƒ(n)/2 n≤lim sup n→∞nƒ(n)/2 n=2 .

## There are no comments yet on this publication. Be the first to share your thoughts.