Automata (DFA / NFA)
Transitions: state,symbol->target, separated by ;. For NFA, use eps as the symbol for an epsilon transition, and multiple comma-separated targets for non-determinism.
Understanding Automata Theory
Automata theory studies abstract machines — simplified computational models — and the languages (sets of strings) they can recognize. A finite automaton is the simplest such machine: a fixed set of states, transitions between them based on input symbols, and rules for which states count as "accepting." These models sit underneath every regular expression engine, lexical analyzer, and simple pattern-matching system in computer science.
Key Definitions & Formulas
- Finite Automaton (FA): a machine with a finite set of states, a start state, accepting states, and transitions.
- Deterministic FA (DFA): exactly one transition per state per input symbol.
- Nondeterministic FA (NFA): a state can have multiple (or zero) transitions for the same symbol; every NFA has an equivalent DFA.
- Regular language: any language recognizable by a finite automaton, equivalently by a regular expression.
- Acceptance: a string is accepted if, starting from the start state and following its symbols, the machine ends in an accepting state.
Worked Example
A DFA that accepts binary strings ending in "1" needs just two states: state A (start, also reached on any 0) and state B (reached on 1, accepting). Reading "101": start at A, read 1 → B, read 0 → A, read 1 → B (accepting) — correctly accepted since the string ends in 1.
Where This Is Used
- Regular expression engines used in text editors, search tools, and programming languages.
- Lexical analysis in compilers (tokenizing source code).
- Network protocol state machines.
- Digital circuit design for sequential logic (finite state machines in hardware).