Deterministic Finite Automaton

A deterministic finite automaton is a state machine that reads an input string one character at a time and transitions between states according to a fixed transition function. For each state and input symbol there is exactly one next state. The machine accepts a string if it ends in an accept state after consuming all input.

In a DFA every (state, symbol) pair has exactly one transition, making execution deterministic. An NFA may have zero, one, or many transitions per pair, and also allows ε-transitions (moves without consuming input). Despite this, DFAs and NFAs recognise exactly the same class of languages — the regular languages.

DFAs recognise exactly the regular languages: those describable by regular expressions or regular grammars. Examples include strings containing a fixed pattern, strings of even length, or binary numbers divisible by a given integer. Languages like {aⁿbⁿ} or balanced parentheses are not regular and cannot be recognised by any DFA.

A sink state is a non-accepting state with self-loops on every alphabet symbol, so once entered the machine can never reach an accept state. Sink states make the transition function total (defined for every input) and are useful for explicitly modelling rejection. You can mark states as sinks with sink: true in this simulator.

Write your DFA as YAML. List the states, alphabet, start state, and accept states, then define transitions either nested under each state or as a flat array. The editor provides syntax highlighting and real-time error feedback. Use the Share button to generate a permalink to your configuration.