Other meanings of Regular language
Computer science
A regular language is a formal language that can be recognized by a finite automaton or generated by a regular expression.1 It is the simplest class in the Chomsky hierarchy, characterized by type-3 grammars, and forms the foundation of lexical analysis, text processing, and pattern matching.2
Regular languages are exactly those languages that can be described by a finite automaton (deterministic or nondeterministic) or a regular expression over a finite alphabet.1 They are also the languages generated by right-linear grammars. The equivalence of these three formalisms is established by Kleene's theorem, which states that a language is regular if and only if it can be expressed by a regular expression. The Myhill–Nerode theorem provides an algebraic characterization: a language is regular if and only if its syntactic monoid is finite, which also gives a minimal deterministic automaton.
The class of regular languages is closed under Boolean operations (union, intersection, complement), concatenation, Kleene star, reversal, homomorphism, and inverse homomorphism.1 It is also closed under quotient operations (left and right). Despite these strong closures, regular languages are not closed under general intersection with context-free languages or under arbitrary substitution. The closure under complement is particularly useful in constructing automata for pattern matching and in proving other languages are not regular via the pumping lemma. The set of all regular languages over a given alphabet forms a Boolean algebra.
Not all languages are regular. The pumping lemma for regular languages gives a necessary condition: any sufficiently long string in a regular language can be pumped (repeated a middle part) and remain in the language.1 This is used to prove languages like anbn (balanced parentheses) are not regular. More powerful criteria exist, such as the Myhill–Nerode theorem, which can characterize exactly when a language is regular. The concept of regular languages is also captured by monadic second-order logic (MSO) over strings: a language is regular iff it is definable by an MSO sentence.3 This equivalence extends to finite automata on infinite words and trees, leading to the theory of ω-regular languages.
Regular languages are ubiquitous in computer science. Lexical analyzers (e.g., Lex, Flex) use regular expressions to tokenize source code.1 Text editors and search engines employ regular expressions for pattern matching. In network security, regular languages model packet signatures and intrusion detection patterns. In bioinformatics, they describe DNA motifs and protein sequences. The algorithmic problem of equivalence of regular expressions, however, is PSPACE-complete, meaning that minimization of regular expressions or automata is computationally hard, though interesting in practice.2
Beyond the standard definition, regular languages exhibit surprising depth. For example, the set of regular languages is not closed under taking the set of prefixes of all strings (the prefix closure) — but it is. Actually, it is closed under prefix, suffix, and substring operations. A less-known fact: not every regular language can be recognized by a deterministic finite automaton with a single cycle of states; the star-free regular languages (those without Kleene star) correspond to languages definable in first-order logic and are exactly those whose syntactic monoid is aperiodic.3 Another edge case: regular languages over a unary alphabet are exactly the eventually periodic sets of natural numbers. The word problem for groups can be regular only for finite groups. In automata theory, the concept of regular languages extends to infinite words (ω-regular languages) used in model checking, and to trees (regular tree languages).
Help improve the encyclopedia. Reports go straight to the site manager.