World Library  
Flag as Inappropriate
Email this Article

Regular language

Article Id: WHEBN0000025723
Reproduction Date:

Title: Regular language  
Author: World Heritage Encyclopedia
Language: English
Subject: Formal language, Abstract family of languages, Recursively enumerable language, Automata theory, Omega-regular language
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Regular language

In theoretical computer science and formal language theory, a regular language (also called a rational language[1][2]) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science. (Many regular expressions engines provided by modern programming languages are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression.)

Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem.[3] In the Chomsky hierarchy, regular languages are defined to be the languages that are generated by Type-3 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 AB (union), AB (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 \{a^nb^n\,\vert\; n\ge 0\}.[4] 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:

  1. it is the language of a regular expression (by the above definition)
  2. it is the language accepted by a nondeterministic finite automaton (NFA)[note 1][note 2]
  3. it is the language accepted by a deterministic finite automaton (DFA)[note 3][note 4]
  4. it can be generated by a regular grammar[note 5][note 6]
  5. it is the language accepted by an alternating finite automaton
  6. it can be generated by a prefix grammar
  7. it can be accepted by a read-only Turing machine
  8. it can be defined in monadic second-order logic (Büchi-Elgot-Trakhtenbrot theorem[5])
  9. it is recognized by some finite monoid, meaning it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet[note 7]

Some authors use one of the above properties different from "1." as 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".[6] Another textbook calls the equivalence of regular expressions and DFAs ("1." and "3." above) "Kleene's theorem".[7] 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").[2][8] 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.[9] Other authors simply define "rational expression" and "regular expressions" as synonymous and do the same with "rational languages" and "regular languages".[1][2]

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:

Deciding whether a language is regular

Regular language in classes of 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 a's as b's is context-free 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.[12]

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 \{ w \in \Sigma^* \, | \, f(w) \in 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

uwL if and only if vwL 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\subset\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). REGULARAC0, 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.[13] On the other hand, REGULAR does not contain AC0, because the nonregular language of palindromes, or the nonregular language \{0^n 1^n : n \in \mathbb N\} can both be recognized in AC0.[14]

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).[15] 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.[16] 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 including complementation but not the Kleene star: this class includes all finite languages.[17]
  • Cyclic languages, satisfying the conditions uv \in L \Leftrightarrow vu \in L and w \in L \Leftrightarrow w^n \in L.[18][19]

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) = \sum_{n \ge 0} s_L(n) z^n \ .

The generating function of a language L is a rational function if L is regular.[18] Hence for any regular language L there exist an integer constant n_0, complex constants \lambda_1,\,\ldots,\,\lambda_k and complex polynomials p_1(x),\,\ldots,\,p_k(x) such that for every n \geq n_0 the number s_L(n) of words of length n in L is s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n.[20][21][22][23]

Thus, non-regularity of certain languages L' can be proved by counting the words of a given length in L'. 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\sim\frac{4^n}{n^{3/2}\sqrt{\pi}}, which is not of the form p(n)\lambda^n, witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvalues \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)\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} \lambda_a^m.[24]

The zeta function of a language L is[18]

\zeta_L(z) = \exp \left({ \sum_{n \ge 0} s_L(n) \frac{z^n}{n} }\right) \ .

The zeta function of a regular language is not in general rational, but that of a cyclic language is.[25][26]

Generalizations

The notion of a regular language has been generalized to infinite words (see ω-automata) and to trees (see tree automaton).

Rational set generalizes the notion (of regular/rational language) to monoids that are not necessarily free. Likewise, the notion of a recognizable language (by a finite automaton) has namesake as recognizable set over a monoid that is not necessarily free. Howard Straubing notes in relation to these facts that “The term "regular language" is a bit unfortunate. Papers influenced by Eilenberg's monograph[27] often use either the term "recognizable language", which refers to the behavior of automata, or "rational language", which refers to important analogies between regular expressions and rational power series. (In fact, Eilenberg defines rational and recognizable subsets of arbitrary monoids; the two notions do not, in general, coincide.) This terminology, while better motivated, never really caught on, and "regular language" is used almost universally.”[28]

Rational series is another generalization, this time in the context of a formal power series over a semiring. This approach gives rise to weighted rational expressions and weighted automata. In this algebraic context, the regular languages (corresponding to Boolean-weighted rational expressions) are usually called rational languages.[29][30] Also in this context, Kleene's theorem finds a generalization called the Kleene-Schützenberger theorem.

See also

Notes

  1. ^ 1. ⇒ 2. by Thompson's construction algorithm
  2. ^ 2. ⇒ 1. by Kleene's algorithm
  3. ^ 2. ⇒ 3. by the powerset construction
  4. ^ 3. ⇒ 2. since the former definition is stronger than the latter
  5. ^ 2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219
  6. ^ 4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218
  7. ^ 3. ⇔ 9. by the Myhill–Nerode theorem

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.
  1. ^ a b
  2. ^ a b c
  3. ^
  4. ^ Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
  5. ^ 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.
  6. ^
  7. ^
  8. ^
  9. ^
  10. ^ Salomaa (1981) p.28
  11. ^ Salomaa (1981) p.27
  12. ^ How to prove that a language is not regular?
  13. ^
  14. ^
  15. ^ 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.
  16. ^ A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.
  17. ^
  18. ^ a b c
  19. ^ Berstel & Reutenauer (2011) p.220
  20. ^ Flajolet & Sedgweick, section V.3.1, equation (13).
  21. ^ Proof of theorem for irreducible DFAs
  22. ^ http://cs.stackexchange.com/a/11333/683 Proof of theorem for arbitrary DFAs
  23. ^ Number of words of a given length in a regular language
  24. ^ Flajolet & Sedgewick (2002) Theorem V.3
  25. ^
  26. ^ Berstel & Reutenauer (2011) p.222
  27. ^ in two volumes "A" (1974, ISBN 9780080873749) and "B" (1976, ISBN 9780080873756), the latter with two chapters by Bret Tilson.
  28. ^
  29. ^ Berstel & Reutenauer (2011) p.47
  30. ^

Further reading

  • Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956); it is a slightly modified version of his 1951 RAND Corporation report of the same title, RM704.

External links

This article was sourced from Creative Commons Attribution-ShareAlike 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, E-Government 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 non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.