A note on a Badly Nondeterministic automaton
Larry H. Reeker · ACM SIGACT News · 1971
A "Badly Nondeterministic" (BN) n-state acceptor is a machine for which any deterministic finite state acceptor for the same language requires 2 n states. A family of such machines, attributed to G. Ott, was described in (1). Taking liberties with the notation of that paper, we will call the family {R n }n>0 (see figure below). Another family of BN automata, which we will call {B n }n>0, was described in (2). These latter BN automata are the subject of this note.