Computer science Automata and formal languages Concept
Deterministic finite automaton
Summary
A deterministic finite automaton (DFA) is a finite-state machine with a set of accepting states. It reads a word symbol by symbol, follows one transition per symbol, and accepts the word when it ends in an accepting state. The languages accepted by DFAs are exactly the regular languages. DFAs are used in lexical analysis, text search and the design of digital circuits.
Where this leads
13 pages build on this one.
- Closure properties of regular languages
- Myhill–Nerode theorem
- Dyck language
- Pumping lemma for regular languages
- Supervisory control theory of discrete event systems
- Powerset construction
- DFA minimization
- Pumping lemma for context-free languages
- Regular language
- Ogden's lemma
- Chomsky–Schützenberger representation theorem
- Two-way finite automaton
- Nondeterministic finite automaton
Further reading
About this page
| Tag | W65B6BKZRY |
|---|---|
| URI | m2://W65B6BKZRY |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q45 |
| Specializes | Finite-state machine |
| Same as | |
| Changed | 3 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
Used by
- Closure properties of regular languages
- Myhill–Nerode theorem
- Pumping lemma for regular languages
- Supervisory control theory of discrete event systems
- Powerset construction
- DFA minimization
- Regular language
- Two-way finite automaton
- Nondeterministic finite automaton