- Regular language
In

theoretical computer science , a**regular language**is aformal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties:

* it can be accepted by adeterministic finite state machine

* it can be accepted by anondeterministic finite state machine

* it can be accepted by analternating finite automaton

* it can be described by a formal regular expression. Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages which are not regular, and are therefore not strictly equivalent to formal regular expressions.

* it can be generated by aregular grammar

* it can be generated by aprefix grammar

* it can be accepted by a read-onlyTuring machine

* it can be defined in monadicsecond-order logic

* it is recognized by some finitely generatedmonoid **Regular languages over an alphabet**The collection of regular languages over an alphabet Σ is defined recursively as follows:

* the empty language Ø is a regular language.

* theempty string language { ε } is a regular language.

* For each "a" ∈ Σ, 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.All finite languages are regular. Other typical examples include the language consisting of all strings over the alphabet {"a", "b"} which contain an even number of "a"s, or the language consisting of all strings of the form: several "a"s followed by several "b"s.

A simple example of a language that is not regular is the set of strings $\{a^nb^n,vert;\; nge\; 0\}$. Some additional examples are given below.

**Complexity results**In

computational complexity theory , thecomplexity class of all regular languages is sometimes referred to as**REGULAR**or**REG**and equalsDSPACE (O(1)), thedecision problem s 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}. [*M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.*] On the other hand, it is not known to contain**AC**^{0}.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). [

*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, DSPACE(o(log log "n")) equals the class of regular languages. In practice, most nonregular problems are solved by machines taking at leastlogarithmic space .**Closure properties**The regular languages are closed under the following operations: That is, if "L" and "P" are regular languages, the following languages are regular as well:

* the complement $ar\{L\}$ of "L"

* theKleene star $L^*$ of "L"

* the image "φ(L)" of "L" under astring homomorphism

* theconcatenation $L\; circ\; P$ of "L" and "P"

* the union $L\; cup\; P$ of "L" and "P"

* the intersection $L\; cap\; P$ of "L" and "P"

* thedifference $L-P$ of "L" and "P"

* the reverse $L^R$ of "L"**Deciding whether a language is regular**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*a*'s as*b*'s is context-free but not regular. To prove that a language such as this is not regular, one uses theMyhill-Nerode theorem or thepumping lemma .There are two purely algebraic approaches to define regular languages. If Σ is a finite alphabet and Σ* denotes the

free monoid over Σ consisting of all strings over Σ, "f" : Σ* → "M" is amonoid homomorphism where "M" is a "finite" monoid, and "S" is a subset of "M", then the set "f"^{ −1}("S") is regular. Every regular language arises in this fashion.If "L" is any subset of Σ*, one defines an

equivalence relation ~ (called thesyntactic 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 thesyntactic monoid ). When a language is regular, then the number of equivalence classes is equal to the number of states of theminimal deterministic finite automaton accepting "L".A similar set of statements can be formulated for a monoid $MsubsetSigma^*$. In this case, equivalence over "M" leads to the concept of a

recognizable language .**Finite languages**A specific subset within the class of regular languages is the finite languages – those containing only a finite number of words. These are obviously regular as one can create a

regular expression that is the union of every word in the language, and thus are regular.**ee also***

Pumping lemma for regular languages **References*** Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.

**External links*** [

*http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#reg REG at Complexity Zoo*]

*Wikimedia Foundation.
2010.*