Regular language

Regular language

In theoretical computer science, a regular language is a formal 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 a deterministic finite state machine
* it can be accepted by a nondeterministic finite state machine
* it can be accepted by an alternating 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 a regular grammar
* 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
* it is recognized by some finitely generated monoid

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.
* the empty 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, 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. [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 AC0.

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 least logarithmic 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"
* the Kleene star L^* of "L"
* the image "φ(L)" of "L" under a string homomorphism
* the concatenation 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"
* the difference 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 the Myhill-Nerode theorem or the pumping 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 a monoid 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 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 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


* Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.

External links

* [ REG at Complexity Zoo]

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Regular Language description for XML — (RELAX) is a specification for describing XML based languages.A description written in RELAX is called a RELAX grammar. RELAX Core has been approved as an ISO/IEC Technical Report 22250 1.RELAX was designed by Murata Makoto. See also *RELAX NG… …   Wikipedia

  • Omega-regular language — The ω regular languages are a class of ω languages which generalize the definition of regular languages to infinite words. Büchi showed in 1962 that ω regular languages are precisely the ones definable in a particular monadic second order logic… …   Wikipedia

  • Regular expression — In computing, a regular expression provides a concise and flexible means for matching (specifying and recognizing) strings of text, such as particular characters, words, or patterns of characters. Abbreviations for regular expression include… …   Wikipedia

  • Regular grammar — Strictly regular grammars = In computer science, a right regular grammar (also called right linear grammar) is a formal grammar ( N , Σ, P , S ) such that all the production rules in P are of one of the following forms: # A → a where A is a non… …   Wikipedia

  • Language attrition — is the loss of a first or second language or a portion of that language by individuals; it should be distinguished from language loss within a community (the latter process is referred to as language shift or language death). Language attrition… …   Wikipedia

  • Language development — is a process that starts early in human life, when a person begins to acquire language by learning it as it is spoken and by mimicry. Children s language development moves from simplicity to complexity. Infants start without language. Yet by four …   Wikipedia

  • Language immersion — is a method of teaching a second language (also called L2, or the target language). Unlike a more traditional language course, where the target language is simply the subject material, language immersion uses the target language as a teaching… …   Wikipedia

  • Language Log — is a collaborative language blog maintained by University of Pennsylvania phonetician Mark Liberman.The site is updated daily at the whims of the contributors, and most of the posts are on language use in the media and popular culture. Google… …   Wikipedia

  • Language identification in the limit — is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title [ amag/langev/paper/gold67limit.html] . In this model, a learner is provided with presentation of some language …   Wikipedia

  • Regular verb — A regular verb is any verb whose conjugation follows the typical grammatical inflections of the language it belongs to.A verb that cannot be conjugated like this is called an irregular verb. All natural languages, to different extents, have a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”