Deterministic Finite Automata (DFA)

a regular language

A regular language is, in one sentence, a language that some DFA recognises. If you can build a finite-state machine whose accepted strings are exactly the strings of the language and no others, then that language is regular. This is the first and simplest rung of a whole ladder of language classes, and it is precisely the set of patterns that bounded, finite memory can check.

The single most important honesty here: regular does NOT mean finite. A regular language can contain infinitely many strings — the language a* (any number of a-s, including zero) is regular and infinite, recognised by a one-state machine that loops on a. 'Regular' means 'recognisable by a finite automaton', a statement about the machine's memory, not about how many strings the language holds. Equivalently (a fact you will meet later), the regular languages are exactly those describable by a regular expression, which is why the name and the regex idea line up.

Regular languages are extremely well behaved: you can decide membership in one pass and constant memory, they are closed under union, intersection, complement and more, and there is a unique smallest DFA for each. Their limit is just the finite-memory limit of the machines that define them — a regular language cannot require counting an unbounded quantity (so { a^n b^n : n >= 0 }, the equal-numbers language, is not regular), but that proof lives in the regular-properties topic, not here.

Regular: 'binary strings ending in 1', 'strings with an even number of a-s', 'strings containing 011 as a substring', 'a*' (infinitely many strings, still regular). Not regular: { a^n b^n : n >= 0 }, because matching unboundedly many a-s to b-s needs more than finite memory.

Regular = recognised by some DFA. Regular does not mean finite (a* is regular and infinite).

Regular is about the machine's bounded memory, not the language's size. Deterministic and nondeterministic finite automata, and regular expressions, all define exactly this same class.

Also called
regular setType-3 language正則語言正規集正規語言