In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are augmented with features that allow the recognition of non-regular languages).
Alternatively, a regular language can be defined as a language recognised by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars.
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 is a regular language. If A is a regular language, A* (Kleene star) is a regular language. Due to this, the empty string language is also regular. If A and B are regular languages, then (union) and (concatenation) are regular languages. No other languages over Σ are regular.
See for syntax and semantics of regular expressions.
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 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 .Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2). 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.
Equivalent formalisms A regular language satisfies the following equivalent properties: it is the language of a regular expression (by the above definition) it is the language accepted by a nondeterministic finite automaton (NFA)1. ⇒ 2. by Thompson's construction algorithm2. ⇒ 1. by Kleene's algorithm or using Arden's lemma it is the language accepted by a deterministic finite automaton (DFA)2. ⇒ 3. by the powerset construction3. ⇒ 2. since the former definition is stronger than the latter it can be generated by a regular grammar2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.2194. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218 it is the language accepted by an alternating finite automaton it is the language accepted by a two-way finite automaton it can be generated by a prefix grammar it can be accepted by a read-only Turing machine it can be defined in monadic second-order logic (Büchi–Elgot–Trakhtenbrot theorem)M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer 2002. it is recognized by some finite syntactic monoid M, meaning it is the preimage of a subset S of a finite monoid M under a monoid homomorphism from the free monoid on its alphabet3. ⇔ 10. by the Myhill–Nerode theorem the number of equivalence classes of its syntactic congruence is finite.u ~ v is defined as: uw ∈ L if and only if vw ∈ L for all w ∈ Σ*3. ⇔ 11. see the proof in the Syntactic monoid article, and see p. 160 in (This number equals the number of states of the minimal deterministic finite automaton accepting L.)
Properties 10. and 11. are purely algebraic approaches to define regular languages; a similar set of statements can be formulated for a monoid . In this case, equivalence over M leads to the concept of a recognizable language.
Some authors use one of the above properties different from "1." as an alternative definition of regular languages.
Some of the equivalences above, particularly those among the first four formalisms, are called Kleene's theorem in textbooks. Precisely which one (or which subset) is called such varies between authors. One textbook calls the equivalence of regular expressions and NFAs ("1." and "2." above) "Kleene's theorem". Another textbook calls the equivalence of regular expressions and DFAs ("1." and "3." above) "Kleene's theorem". Two other textbooks first prove the expressive equivalence of NFAs and DFAs ("2." and "3.") and then state "Kleene's theorem" as the equivalence between regular expressions and finite automata (the latter said to describe "recognizable languages"). A linguistically oriented text first equates regular grammars ("4." above) with DFAs and NFAs, calls the languages generated by (any of) these "regular", after which it introduces regular expressions which it terms to describe "rational languages", and finally states "Kleene's theorem" as the coincidence of regular and rational languages. Other authors simply define "rational expression" and "regular expressions" as synonymous and do the same with "rational languages" and "regular languages".
Apparently, the term regular originates from a 1951 technical report where Kleene introduced regular events and explicitly welcomed "any suggestions as to a more descriptive term". Here: p.46 Noam Chomsky, in his 1959 seminal article, used the term regular in a different meaning at first (referring to what is called Chomsky normal form today), Here: Definition 8, p.149 but noticed that his finite state languages were equivalent to Kleene's regular events.Chomsky 1959, Footnote 10, p.150
Closure properties The regular languages are closed under 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 , intersection , and complement , hence also relative complement .Salomaa (1981) p.28 the regular operations: , concatenation , and Kleene star .Salomaa (1981) p.27 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) LR.Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72 Given a nondeterministic finite automaton to recognize L, an automaton for LR can be obtained by reversing all transitions and interchanging starting and finishing states. This may result in multiple starting states; ε-transitions can be used to join them.
Decidability properties Given two deterministic finite automata A and B, it is decidable whether they accept the same language.Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67 As a consequence, using the above closure properties, the following problems are also decidable for arbitrarily given deterministic finite automata A and B, with accepted languages LA and LB, respectively: Containment: is LA ⊆ LB ?Check if LA ∩ LB = LA. Deciding this property is NP-hard in general; see :File:RegSubsetNP.pdf for an illustration of the proof idea. Disjointness: is LA ∩ LB = ? Emptiness: is LA = ? Universality: is LA = Σ* ? Membership: given a ∈ Σ*, is a ∈ LB ?
For regular expressions, the universality problem is NP-complete already for a singleton alphabet.Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401 For larger alphabets, that problem is PSPACE-complete.Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399 If regular expressions are extended to allow also a squaring operator, with "A2" denoting the same as "AA", still just regular languages can be described, but the universality problem has an exponential space lower bound,Hopcroft, Ullman (1979), Theorem 13.15, p.351 and is in fact complete for exponential space with respect to polynomial-time reduction.Hopcroft, Ullman (1979), Corollary p.353
For a fixed finite alphabet, the theory of the set of all languages – together with strings, membership of a string in a language, and for each character, a function to append the character to a string (and no other operations) – is decidable, and its minimal elementary substructure consists precisely of regular languages. For a binary alphabet, the theory is called S2S.
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 ≠ AC0, 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 AC0. On the other hand, REGULAR does not contain AC0, because the nonregular language of palindromes, or the nonregular language can both be recognized in AC0.
If a language is not regular, it requires a machine with at least space to recognize (where n is the input size).J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, pp. 179–190. 1965. In other words, equals the class of regular languages. In fact, the result shown is slightly stronger: any Turing machine running in space and terminating on all inputs must actually run in constant space. In practice, most nonregular problems are studied in a setting with at least logarithmic space, as this is the amount of space required to store a pointer into the input tape.Sipser (1997) p.349
Location in the Chomsky hierarchy
To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is context-free. The converse is not true: for example, the language consisting of all strings having the same number of as as bs is context-free but not regular. To prove that a language is not regular, one often uses the Myhill–Nerode theorem and the pumping lemma. Other approaches include using the closure properties of regular languages or quantifying Kolmogorov complexity.
Important subclasses of regular languages include: Finite languages, those containing only a finite number of words.A finite language should not be confused with a (usually infinite) language generated by a finite automaton. These are regular languages, as one can create a regular expression that is the union of every word in the language. Star-free languages, those that can be described by a regular expression constructed from the empty symbol, letters, concatenation and all Boolean operators (see algebra of sets) including complementation but not the Kleene star: this class includes all finite languages.
Number of words in a regular language Let denote the number of words of length in . The ordinary generating function for L is the formal power series
The generating function of a language L is a rational function if L is regular. Hence for every regular language the sequence is constant-recursive; that is, there exist an integer constant , complex constants and complex polynomials such that for every the number of words of length in is .Flajolet & Sedgweick, section V.3.1, equation (13).
Thus, non-regularity of certain languages can be proved by counting the words of a given length in . Consider, for example, the Dyck language of strings of balanced parentheses. The number of words of length in the Dyck language is equal to the Catalan number , which is not of the form ,