regular language

Uses your system voice; voice and rate in settings.

Q752532Snapshot

≈ 5 min read

Names in other languages

  • Русскийрегулярное множество
  • Françaislangage rationnel
  • Portuguêslinguagem regular
  • Englishregular language
  • Polskijęzyk regularny
  • עבריתשפה רגולרית
  • 简体中文正则语言
  • 繁體中文正則語言
  • 中文正則語言

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. Disjointness: is L A ∩ L B = ? Emptiness: is L A = ? Universality: is L A = Σ * ? Membership: given a ∈ Σ * , is a ∈ L B ? For regular expressions, the universality problem is NP-complete already for a singleton alphabet. For larger alphabets, that problem is PSPACE-complete. If regular expressions are extended to allow also a squaring operator, with "A 2 " denoting the same as "AA", still just regular languages can be described, but the universality problem has an exponential space lower bound, and is in fact complete for exponential space with respect to polynomial-time reduction. 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.

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. 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. 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. Hence for every regular language L the sequence s_L(n)_{n \geq 0} is constant-recursive; that is, 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 . 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 . The zeta function of a language L is \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 an arbitrary cyclic language is.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378659155 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot regular-language-086374-95d9fc12b0e392d8 · hash 95d9fc12b0e392d84d0e6d59827ecfbdf3658a9b3791e5d733c961e9432a3849 · captured 1791203166.0 · version history

Cite this page as: encyclopegia.org, “regular language”, snapshot regular-language-086374-95d9fc12b0e392d8. https://encyclopegia.org/a/regular-language

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.