In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using a regular expression. (Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages that can not be expressed by the formal regular expressions (as formally defined below).)
Alternatively, a regular language can be defined as a language recognized by a finite automaton.
In the Chomsky hierarchy, regular languages are defined to be the languages that are generated by Type3 grammars (regular grammars).
Regular languages are very useful in input parsing and programming language design.
Formal definition
The collection of regular languages over an alphabet Σ is defined recursively as follows:
 The empty language Ø is a regular language.
 For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
 If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
 No other languages over Σ are regular.
See regular expression for its syntax and semantics. Note that the above cases are in effect the defining rules of regular expression.
 Examples
All finite languages are regular; in particular the empty string language {ε} = Ø* is regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of as, or the language consisting of all strings of the form: several as followed by several bs.
A simple example of a language that is not regular is the set of strings $\backslash \{a^nb^n\backslash ,\backslash vert\backslash ;\; n\backslash ge\; 0\backslash \}$.^{[1]} Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given below.
Equivalence to other formalisms
A regular language satisfies the following equivalent properties:
The above properties are sometimes used as alternative definition of regular languages.
Closure properties
The regular languages are closed under the various operations, that is, if the languages K and L are regular, so is the result of the following operations:
 the set theoretic Boolean operations: union $K\; \backslash cup\; L$, intersection $K\; \backslash cap\; L$, and complement $\backslash bar\{L\}$. From this also relative complement $KL$ follows.^{[3]}
 the regular operations: union $K\; \backslash cup\; L$, concatenation $K\backslash circ\; L$, and Kleene star $L^*$.^{[4]}
 the trio operations: string homomorphism, inverse string homomorphism, and intersection with regular languages. As a consequence they are closed under arbitrary finite state transductions, like quotient $K\; /\; L$ with a regular language. Even more, regular languages are closed under quotients with arbitrary languages: If L is regular then L/K is regular for any K.
 the reverse (or mirror image) $L^R$.
Deciding whether a language is regular
To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is contextfree. The converse is not true: for example the language consisting of all strings having the same number of a's as b's is contextfree but not regular. To prove that a language such as this is not regular, one often uses the Myhill–Nerode theorem or the pumping lemma among other methods.^{[5]}
There are two purely algebraic approaches to define regular languages. If:
 Σ is a finite alphabet,
 Σ* denotes the free monoid over Σ consisting of all strings over Σ,
 f : Σ* → M is a monoid homomorphism where M is a finite monoid,
 S is a subset of M
then the set $\backslash \{\; w\; \backslash in\; \backslash Sigma^*\; \backslash ,\; \; \backslash ,\; f(w)\; \backslash in\; S\; \backslash \}$ is regular. Every regular language arises in this fashion.
If L is any subset of Σ*, one defines an equivalence relation ~ (called the syntactic relation) on Σ* as follows: u ~ v is defined to mean
 uw ∈ L if and only if vw ∈ L for all w ∈ Σ*
The language L is regular if and only if the number of equivalence classes of ~ is finite (A proof of this is provided in the article on the syntactic monoid). When a language is regular, then the number of equivalence classes is equal to the number of states of the minimal deterministic finite automaton accepting L.
A similar set of statements can be formulated for a monoid $M\backslash subset\backslash Sigma^*$. In this case, equivalence over M leads to the concept of a recognizable language.
Complexity results
In computational complexity theory, the complexity class of all regular languages is sometimes referred to as REGULAR or REG and equals DSPACE(O(1)), the decision problems that can be solved in constant space (the space used is independent of the input size). REGULAR ≠ AC^{0}, since it (trivially) contains the parity problem of determining whether the number of 1 bits in the input is even or odd and this problem is not in AC^{0}.^{[6]} On the other hand, REGULAR does not contain AC^{0}, because the nonregular language of palindromes, or the nonregular language $\backslash \{0^n\; 1^n:\; n\; \backslash in\; \backslash mathbb\; N\backslash \}$ can both be recognized in AC^{0}.^{[7]}
If a language is not regular, it requires a machine with at least Ω(log log n) space to recognize (where n is the input size).^{[8]} In other words, DSPACE(o(log log n)) equals the class of regular languages. In practice, most nonregular problems are solved by machines taking at least logarithmic space.
Subclasses
Important subclasses of regular languages include
 Finite languages  those containing only a finite number of words. These are regular languages, as one can create a regular expression that is the union of every word in the language.
 Starfree languages, those that can be described by a regular expression constructed from the empty symbol, letters, concatenation and all boolean operators including complementation but not the Kleene star: this class includes all finite languages.^{[9]}
 Cyclic languages, satisfying the conditions $uv\; \backslash in\; L\; \backslash Leftrightarrow\; vu\; \backslash in\; L$ and $w\; \backslash in\; L\; \backslash Leftrightarrow\; w^n\; \backslash in\; L$.^{[10]}
The number of words in a regular language
Let $s\_L(n)$ denote the number of words of length $n$ in $L$. The ordinary generating function for L is the formal power series
 $S\_L(z)\; =\; \backslash sum\_\{n\; \backslash ge\; 0\}\; s\_L(n)\; z^n\; \backslash \; .$
The generating function of a language L is a rational function if L is regular.^{[10]} Hence for any regular language $L$ there exist an integer constant $n\_0$, complex constants $\backslash lambda\_1,\backslash ,\backslash ldots,\backslash ,\backslash lambda\_k$ and complex polynomials $p\_1(x),\backslash ,\backslash ldots,\backslash ,p\_k(x)$
such that for every $n\; \backslash geq\; n\_0$ the number $s\_L(n)$ of words of length $n$ in $L$ is
$s\_L(n)=p\_1(n)\backslash lambda\_1^n+\backslash dotsb+p\_k(n)\backslash lambda\_k^n$.^{[11]}^{[12]}^{[13]}^{[14]}
Thus, nonregularity of certain languages $L\text{'}$ can be proved by counting the words of a given length in
$L\text{'}$. Consider, for example, the Dyck language of strings of balanced parentheses. The number of words of length $2n$
in the Dyck language is equal to the Catalan number $C\_n\backslash sim\backslash frac\{4^n\}\{n^\{3/2\}\backslash sqrt\{\backslash pi\}\}$, which is not of the form $p(n)\backslash lambda^n$,
witnessing the nonregularity of the Dyck language. Care must be taken since some of the eigenvalues $\backslash lambda\_i$ could have the same magnitude. For example, the number of words of length $n$ in the language of all even binary words is not of the form $p(n)\backslash lambda^n$, but the number of words of even or odd length are of this form; the corresponding eigenvalues are $2,2$. In general, for every regular language there exists a constant $d$ such that for all $a$, the number of words of length $dm+a$ is asymptotically $C\_a\; m^\{p\_a\}\; \backslash lambda\_a^m$.^{[15]}
The zeta function of a language L is^{[10]}
 $\backslash zeta\_L(z)\; =\; \backslash exp\; \backslash left(\{\; \backslash sum\_\{n\; \backslash ge\; 0\}\; s\_L(n)\; \backslash frac\{z^n\}\{n\}\; \}\backslash right)\; \backslash \; .$
The zeta function of a regular language is not in general rational, but that of a cyclic language is.^{[16]}
Generalizations
The notion of a regular language has been generalized to infinite words (see ωautomata) and to trees (see tree automaton).
See also
References


 Chapter 1: Regular Languages, pp. 31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
 Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics: Symbolic Combinatorics. Online book, 2002.
External links


   Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it. 

This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.