Computer science Automata and formal languages Concept
Regular language
Summary
A regular language is a formal language that some deterministic finite automaton accepts. By Kleene's theorem, these are also the languages described by regular expressions. Regular languages form the lowest level of the Chomsky hierarchy and have very good closure properties and decision procedures. They are recognized with a fixed amount of memory, whatever the length of the input.
Where this leads
16 pages build on this one.
- Closure properties of regular languages
- Parikh's theorem
- Myhill–Nerode theorem
- Dyck language
- Deterministic context-free language
- Context-free language
- Pumping lemma for regular languages
- Chomsky hierarchy
- DFA minimization
- Kleene's theorem
- Omega-regular language
- Pumping lemma for context-free languages
- Ogden's lemma
- Chomsky–Schützenberger representation theorem
- Two-way finite automaton
- Schützenberger's theorem on star-free languages
Further reading
About this page
| Tag | 18WVBDCS38 |
|---|---|
| URI | m2://18WVBDCS38 |
| Kind | concept |
| Writing | W0 stub |
| MSC | 68Q45 |
| Specializes | Formal language |
| 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
Results about this
- Closure properties of regular languages
- Myhill–Nerode theorem
- Pumping lemma for regular languages
- Kleene's theorem
Used by
- Closure properties of regular languages
- Parikh's theorem
- Myhill–Nerode theorem
- Dyck language
- Deterministic context-free language
- Context-free language
- Pumping lemma for regular languages
- Chomsky hierarchy
- DFA minimization
- Kleene's theorem
- Omega-regular language
- Chomsky–Schützenberger representation theorem
- Two-way finite automaton
- Schützenberger's theorem on star-free languages