Finite State Machine Builder

A finite automaton is a mathematical model of computation with a finite number of states. It reads an input string one symbol at a time, transitioning between states according to a set of rules.

Formally, a finite automaton is a 5-tuple:

where Q is the set of states, $\Sigma$ is the input alphabet, $\delta$ is the transition function, $q_0$ is the start state, and F is the set of accept states.

A DFA (Deterministic Finite Automaton) has exactly one transition per state per symbol. For every state and every input symbol, the next state is uniquely determined.

An NFA (Nondeterministic Finite Automaton) allows multiple transitions for the same symbol from a single state. It accepts if any possible path leads to an accept state.

Both DFA and NFA recognize exactly the same class of languages, the regular languages. Every NFA can be converted to an equivalent DFA (though the DFA may have exponentially more states).

The transition function defines how the machine moves between states. For a DFA it maps a state and input symbol to exactly one next state:

For an NFA, the transition function maps to a set of possible next states:

A transition is written as $\delta(q_0, a) = q_1$, meaning "from state $q_0$, on input $a$, go to state $q_1$".

A language is regular if some finite automaton recognizes it. Regular languages are closed under union, intersection, complement, concatenation, and Kleene star.

Examples of regular languages include "binary strings divisible by 3", "strings ending in ab", and "strings with an even number of 0s". All of these can be expressed as regular expressions and recognized by finite automata.

Not all languages are regular. For instance, the language of balanced parentheses requires a pushdown automaton (stack), making it context-free but not regular.