Finite State Automaton Challenges

Finite State Automaton Challenges gives you 80 puzzles to solve by designing finite state automata. The challenges cover character strings, binary numbers and everyday situations, and a tutorial introduces the concepts.

Design automata

A finite state automaton consists of states and transition rules that describe how it moves between states. You use one to decide which input strings are accepted or rejected; for example, an automaton can recognize valid emails or phone numbers. Challenges include building automata that accept the string "ab" or either "a" or "b".

The game also features levels with different kinds of states, beyond the traditional begin, accept and normal states. Some puzzles use non-deterministic finite state automata: an input is accepted if at least one possible path through the automaton ends in an accepting state. This lets the automaton make guesses as it processes a string.