A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A language is regular if and only if it is recognized by some finite automaton (equivalently, expressible as a regular expression, or describable by a right-linear grammar). Regular languages form the simplest class in the Chomsky hierarchy and are fundamental to pattern matching and lexical analysis.
From your work with DFAs, you know that a finite automaton reads input one symbol at a time, transitions between a fixed set of states, and accepts or rejects based on whether it ends in an accepting state. A regular language is any language that some finite automaton can recognize. This definition sounds simple, but it pins down exactly which patterns can be detected with finite memory — no stack, no tape, just a fixed number of states.
The remarkable fact is that three very different-looking formalisms define exactly the same class of languages. A language is regular if and only if it can be described by a regular expression (built from concatenation, union, and the Kleene star), recognized by a DFA or NFA, or generated by a right-linear grammar. These equivalences mean you can move freely between representations depending on what's convenient: regular expressions are compact and human-readable, DFAs are efficient to execute, and NFAs are often easier to construct. The subset construction you've studied converts any NFA to a DFA, proving their equivalence.
Regular languages sit at the bottom of the Chomsky hierarchy, which classifies languages by the computational power needed to recognize them. Above regular languages are context-free languages (recognized by pushdown automata), context-sensitive languages, and recursively enumerable languages (recognized by Turing machines). What makes regular languages special is their simplicity: recognizing them requires only constant memory. A DFA with *n* states can process an input string of any length — a million characters, a billion — using the same fixed set of states. This makes them extraordinarily efficient and is why regular expressions power lexical analyzers in compilers, text search tools like grep, and input validation in virtually every programming language.
Understanding what regular languages *cannot* do is equally important. Because a finite automaton has fixed memory, it cannot count or match unbounded patterns. The language {aⁿbⁿ | n ≥ 0} — strings with equal numbers of a's followed by b's — is not regular, because recognizing it requires remembering how many a's were seen, which can grow without bound. The pumping lemma (which you'll encounter next) formalizes this limitation, giving you a tool to prove that specific languages fall outside the regular class. Knowing the boundary of regular languages tells you when a finite automaton will suffice and when you need a more powerful computational model.