Frequently Asked Questions

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.

An NFA is a state machine where each (state, symbol) pair can have zero, one, or many transitions, and execution may branch into multiple simultaneous states. The machine accepts a string if any branch of execution ends in an accept state. NFAs are often easier to construct than equivalent DFAs.

An epsilon transition allows the automaton to move to another state without consuming any input character. NFAs can use ε-transitions to "jump" between states freely, which is useful for composing sub-machines. The simulator automatically computes ε-closures when stepping through execution.

Yes. For every NFA there exists a DFA that recognises the same language, via the subset construction (powerset construction). The resulting DFA may have exponentially more states in the worst case, but the recognised language is identical. Both models define exactly the class of regular languages.

The simulator tracks the full set of active states at each step, including ε-closure expansion. You can see which states are simultaneously active and how they evolve as each input symbol is consumed. Acceptance is shown once all input has been read and at least one active state is an accept state.

An NFA accepts a string if there exists at least one sequence of transitions — following the input symbols and any ε-transitions — that leads from the start state to an accept state after consuming all input. It is enough for one branch to succeed; all other branches may reject or get stuck.

A Turing machine is a mathematical model of computation consisting of an infinite tape divided into cells, a read/write head, a finite set of states, and a transition function. At each step the machine reads the current cell, writes a symbol, moves the head left or right, and transitions to a new state. Turing machines can compute anything a modern computer can.

A Turing machine accepts its input by entering a designated accept state, and rejects by entering a reject state. Unlike DFAs, a Turing machine may also run forever without halting — this is called looping. The halting problem (deciding whether a machine halts on a given input) is undecidable.

A multi-tape Turing machine has several independent tapes each with its own read/write head. Multiple tapes can make programs significantly easier to write, but every multi-tape machine can be simulated by a single-tape machine — so the two models recognise exactly the same class of languages.

Each tape can be configured as infinite (extends in both directions), left-bounded (a fixed left end, like a standard TM), right-bounded, or both-bounded (finite tape). The boundary setting is per-tape and can be changed in Tape Settings before running the machine.

The Church-Turing thesis is the hypothesis that any function computable by an effective algorithm can be computed by a Turing machine. It is a thesis rather than a theorem — it cannot be formally proved — but decades of research have found no counterexamples, and all known models of general computation are equivalent in power.

A context-free grammar is a formal grammar with production rules that replace a single non-terminal symbol with a string of terminals and non-terminals. CFGs describe context-free languages and are widely used to define the syntax of programming languages. They are strictly more expressive than regular grammars (DFA/NFA).

Chomsky Normal Form is a restricted form of CFG where every rule is either A → BC (two non-terminals) or A → a (one terminal). Any CFG can be converted to CNF without changing the language it generates. CNF is required by the CYK algorithm used in this simulator.

The Cocke–Younger–Kasami (CYK) algorithm is a dynamic programming algorithm that decides whether a string belongs to a context-free language. It fills an n×n triangular table of substrings bottom-up and runs in O(n³ · |G|) time, where n is the input length and |G| is the grammar size.

A derivation tree (or parse tree) shows how a string is derived from the start symbol step by step. Each internal node is a non-terminal, each leaf is a terminal character, and the children of each node match the right-hand side of the production rule applied at that step. This simulator reconstructs one valid derivation tree whenever the input is accepted.

CFGs describe context-free languages, which properly include all regular languages. Classic non-regular examples are {aⁿbⁿ | n ≥ 1} (equal counts of a and b), balanced parentheses, and arithmetic expressions. However, CFLs cannot describe {aⁿbⁿcⁿ} — that requires a more powerful model such as a Turing machine.