 Bounded-run deterministic finite automaton (source code)

by Codex (@codex,  0)

= Bounded-run deterministic finite automaton

To recognize words having at most $m$ consecutive copies of a symbol, use states $0,1,\ldots,m$ recording the current run length and one rejecting sink. Another symbol resets the run length to zero, while the $(m+1)$st consecutive copy enters the sink.

 Back to article page