Regular language - wikipedia Regular language For natural language that is regulated, see List of language regulators. `` Kleene 's theorem '' redirects here. For his theorems for recursive functions, see Kleene 's recursion theorem. In theoretical computer science and formal language theory, a regular language ( also called a rational language ) 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 ( as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that can not 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 ( after American mathematician Stephen Cole Kleene ). 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. Contents 1 Formal definition 2 Examples 3 Equivalent formalisms 4 Closure properties 5 Decidability properties 6 Complexity results 7 Location in the Chomsky hierarchy 8 The number of words in a regular language 9 Generalizations 10 Notes 11 References 12 Further reading 13 External links Formal definition The collection of regular languages over an alphabet Σ is defined recursively as follows : The empty language Ø, and the empty string language ( ε ) are regular languages. For each a ∈ Σ ( a belongs to Σ ), 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. 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 b n ≥ 0 ). Intuitively, it can not be recognized with a finite automaton, since a finite automaton has finite memory and it can not 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 ) it is the language accepted by a deterministic finite automaton ( DFA ) it can be generated by a regular grammar it is the language accepted by an alternating 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 ) it is recognized by some finite monoid M, meaning it is the preimage ( w ∈ Σ f ( w ) ∈ S ) of a subset S of a finite monoid M under a monoid homomorphism f : Σ → M from the free monoid on its alphabet the number of equivalence classes of its `` syntactic relation '' ~ is finite ( this number equals the number of states of the minimal deterministic finite automaton accepting L. ) Properties 9. and 10. are purely algebraic approaches to define regular languages ; a similar set of statements can be formulated for a monoid M ⊂ Σ. 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 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 ''. 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 : the set theoretic Boolean operations : union K ∪ L, intersection K ∩ L, and complement L, hence also relative complement K - L. the regular operations : K ∪ L, concatenation K ∘ L, and Kleene star L. 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 ) L. Decidability properties Given two deterministic finite automata A and B, it is decidable whether they accept the same language. 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 L and L, respectively : Containment : is L ⊆ L ? Disjointness : is L ∩ L = ( ) ? Emptiness : is L = ( ) ? Universality : is L = Σ ? Membership : given a ∈ Σ, is a ∈ L ? 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 '' 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. 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 ≠ AC, 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. On the other hand, REGULAR does not contain AC, because the nonregular language of palindromes, or the nonregular language ( 0 n 1 n : n ∈ N ) ( displaystyle ( 0 ^ ( n ) 1 ^ ( n ) : n in mathbb ( N ) ) ) can both be recognized in AC. 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 ). 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. Location in the Chomsky hierarchy 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. 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 including complementation but not the Kleene star : this class includes all finite languages. Cyclic languages, satisfying the conditions uv ∈ L ⇔ vu ∈ L and w ∈ L ⇔ w ∈ L. The number of words in a regular language Let s L ( n ) ( displaystyle s_ ( L ) ( n ) ) denote the number of words of length n ( displaystyle n ) in L ( displaystyle L ). The ordinary generating function for L is the formal power series S L ( z ) = ∑ n ≥ 0 s L ( n ) z n. ( displaystyle S_ ( L ) ( z ) = sum _ ( n geq 0 ) s_ ( L ) ( n ) z ^ ( n ) . ) The generating function of a language L is a rational function if L is regular. Hence for any regular language L ( displaystyle L ) there exist an integer constant n 0 ( displaystyle n_ ( 0 ) ), complex constants λ 1,..., λ k ( displaystyle lambda _ ( 1 ), , ldots, , lambda _ ( k ) ) and complex polynomials p 1 ( x ),..., p k ( x ) ( displaystyle p_ ( 1 ) ( x ), , ldots, , p_ ( k ) ( x ) ) such that for every n ≥ n 0 ( displaystyle n geq n_ ( 0 ) ) the number s L ( n ) ( displaystyle s_ ( L ) ( n ) ) of words of length n ( displaystyle n ) in L ( displaystyle L ) is s L ( n ) = p 1 ( n ) λ 1 n + ⋯ + p k ( n ) λ k n ( displaystyle s_ ( L ) ( n ) = p_ ( 1 ) ( n ) lambda _ ( 1 ) ^ ( n ) + dotsb + p_ ( k ) ( n ) lambda _ ( k ) ^ ( n ) ). Thus, non-regularity of certain languages L ′ ( displaystyle L ' ) can be proved by counting the words of a given length in L ′ ( displaystyle L ' ). Consider, for example, the Dyck language of strings of balanced parentheses. The number of words of length 2 n ( displaystyle 2n ) in the Dyck language is equal to the Catalan number C n ∼ 4 n n 3 / 2 π ( displaystyle C_ ( n ) sim ( \frac ( 4 ^ ( n ) ) ( n ^ ( 3 / 2 ) ( sqrt ( pi ) ) ) ) ), which is not of the form p ( n ) λ n ( displaystyle p ( n ) lambda ^ ( n ) ), witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvalues λ i ( displaystyle lambda _ ( i ) ) could have the same magnitude. For example, the number of words of length n ( displaystyle n ) in the language of all even binary words is not of the form p ( n ) λ n ( displaystyle p ( n ) lambda ^ ( n ) ), but the number of words of even or odd length are of this form ; the corresponding eigenvalues are 2, − 2 ( displaystyle 2, - 2 ). In general, for every regular language there exists a constant d ( displaystyle d ) such that for all a ( displaystyle a ), the number of words of length d m + a ( displaystyle dm + a ) is asymptotically C a m p a λ a m ( displaystyle C_ ( a ) m ^ ( p_ ( a ) ) lambda _ ( a ) ^ ( m ) ). The zeta function of a language L is ζ L ( z ) = exp ⁡ ( ∑ n ≥ 0 s L ( n ) z n n ). ( displaystyle zeta _ ( L ) ( z ) = exp left ( ( sum _ ( n geq 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. 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 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. '' 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. Also in this context, Kleene 's theorem finds a generalization called the Kleene - Schützenberger theorem. Notes Jump up ^ 1. ⇒ 2. by Thompson 's construction algorithm Jump up ^ 2. ⇒ 1. by Kleene 's algorithm Jump up ^ 2. ⇒ 3. by the powerset construction Jump up ^ 3. ⇒ 2. since the former definition is stronger than the latter Jump up ^ 2. ⇒ 4. see Hopcroft, Ullman ( 1979 ), Theorem 9.2, p. 219 Jump up ^ 4. ⇒ 2. see Hopcroft, Ullman ( 1979 ), Theorem 9.1, p. 218 Jump up ^ 3. ⇔ 9. by the Myhill -- Nerode theorem Jump up ^ u ~ v is defined as : uw ∈ L if and only if vw ∈ L for all w ∈ Σ Jump up ^ 3. ⇔ 10. see the proof in the Syntactic monoid article, and see p. 160 in Holcombe, W.M.L. ( 1982 ). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. 1. Cambridge University Press. ISBN 0 - 521 - 60492 - 3. Zbl 0489.68046. Jump up ^ Check if L ∩ L = L. Deciding this property is NP - hard in general ; see File : RegSubsetNP. pdf for an illustration of the proof idea. References Berstel, Jean ; Reutenauer, Christophe ( 2011 ). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. 137. Cambridge : Cambridge University Press. ISBN 978 - 0 - 521 - 19022 - 0. Zbl 1250.68007. Eilenberg, Samuel ( 1974 ). Automata, Languages, and Machines. Volume A. Pure and Applied Mathematics. 58. New York : Academic Press. Zbl 0317.94045. Salomaa, Arto ( 1981 ). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0 - 273 - 08522 - 0. Zbl 0487.68064. Sipser, Michael ( 1997 ). Introduction to the Theory of Computation. PWS Publishing. ISBN 0 - 534 - 94728 - X. Zbl 1169.68300. 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. John E. Hopcroft ; Jeffrey D. Ullman ( 1979 ). Introduction to Automata Theory, Languages, and Computation. Addison - Wesley. ISBN 0 - 201 - 02988 - X. Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman ( 1974 ). The Design and Analysis of Computer Algorithms. Addison - Wesley. ^ Jump up to : Ruslan Mitkov ( 2003 ). The Oxford Handbook of Computational Linguistics. Oxford University Press. p. 754. ISBN 978 - 0 - 19 - 927634 - 9. ^ Jump up to : Mark V. Lawson ( 2003 ). Finite Automata. CRC Press. pp. 98 -- 103. ISBN 978 - 1 - 58488 - 255 - 8. Jump up ^ Sheng Yu ( 1997 ). `` Regular languages ''. In Grzegorz Rozenberg ; Arto Salomaa. Handbook of Formal Languages : Volume 1. Word, Language, Grammar. Springer. p. 41. ISBN 978 - 3 - 540 - 60420 - 4. Jump up ^ Eilenberg ( 1974 ), p. 16 ( Example II, 2.8 ) and p. 25 ( Example II, 5.2 ). Jump up ^ 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. Jump up ^ Robert Sedgewick ; Kevin Daniel Wayne ( 2011 ). Algorithms. Addison - Wesley Professional. p. 794. ISBN 978 - 0 - 321 - 57351 - 3. Jump up ^ Jean - Paul Allouche ; Jeffrey Shallit ( 2003 ). Automatic Sequences : Theory, Applications, Generalizations. Cambridge University Press. p. 129. ISBN 978 - 0 - 521 - 82332 - 6. Jump up ^ Kenneth Rosen ( 2011 ). Discrete Mathematics and Its Applications 7th edition. McGraw - Hill Science. pp. 873 -- 880. Jump up ^ Horst Bunke ; Alberto Sanfeliu ( January 1990 ). Syntactic and Structural Pattern Recognition : Theory and Applications. World Scientific. p. 248. ISBN 978 - 9971 - 5 - 0566 - 0. Jump up ^ Salomaa ( 1981 ) p. 28 Jump up ^ Salomaa ( 1981 ) p. 27 Jump up ^ Hopcroft, Ullman ( 1979 ), Theorem 3.8, p. 64 ; see also Theorem 3.10, p. 67 Jump up ^ Aho, Hopcroft, Ullman ( 1974 ), Exercise 10.14, p. 401 Jump up ^ Hunt, H.B., III ( 1973 ), `` On the time and tape complexity of languages. I '', Fifth Annual ACM Symposium on Theory of Computing ( Austin, Tex., 1973 ), Assoc. Comput. Mach., New York, pp. 10 -- 19, MR 0421145 Jump up ^ Harry Bowen ( Hunt III ) ( Aug 1973 ). On the Time and Tape Complexity of Languages ( PDF ) ( Ph. D. thesis ). TR. 73 - 182. Cornell University. Jump up ^ Hopcroft, Ullman ( 1979 ), Theorem 13.15, p. 351 Jump up ^ A.R. Meyer & L.J. Stockmeyer ( Oct 1972 ). The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space ( PDF ). 13th Annual IEEE Symp. on Switching and Automata Theory. pp. 125 -- 129. Jump up ^ L.J. Stockmeyer & A.R. Meyer ( 1973 ). Word Problems Requiring Exponential Time ( PDF ). Proc. 5th ann. symp. on Theory of computing ( STOC ). ACM. pp. 1 -- 9. Jump up ^ Hopcroft, Ullman ( 1979 ), Corollary p. 353 Jump up ^ Furst, Merrick ; Saxe, James B. ; Sipser, Michael ( 1984 ). `` Parity, circuits, and the polynomial - time hierarchy ''. Mathematical Systems Theory. 17 ( 1 ) : 13 -- 27. MR 738749. doi : 10.1007 / BF01744431. Jump up ^ Cook, Stephen ; Nguyen, Phuong ( 2010 ). Logical foundations of proof complexity ( 1. publ. ed. ). Ithaca, NY : Association for Symbolic Logic. p. 75. ISBN 0 - 521 - 51729 - X. Jump up ^ 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. Jump up ^ How to prove that a language is not regular ? Jump up ^ A finite language should n't be confused with a ( usually infinite ) language generated by a finite automaton. Jump up ^ Volker Diekert ; Paul Gastin ( 2008 ). `` First - order definable languages ''. In Jörg Flum ; Erich Grädel ; Thomas Wilke. Logic and automata : history and perspectives ( PDF ). Amsterdam University Press. ISBN 978 - 90 - 5356 - 576 - 6. ^ Jump up to : Honkala, Juha ( 1989 ). `` A necessary condition for the rationality of the zeta function of a regular language '' ( PDF ). Theor. Comput. Sci. 66 ( 3 ) : 341 -- 347. Zbl 0675.68034. doi : 10.1016 / 0304 - 3975 ( 89 ) 90159 - x. More than one of number = and issue = specified ( help ) Jump up ^ Berstel & Reutenauer ( 2011 ) p. 220 Jump up ^ Flajolet & Sedgweick, section V. 3.1, equation ( 13 ). Jump up ^ Proof of theorem for irreducible DFAs Jump up ^ http://cs.stackexchange.com/a/11333/683 Proof of theorem for arbitrary DFAs Jump up ^ Number of words of a given length in a regular language Jump up ^ Flajolet & Sedgewick ( 2002 ) Theorem V. 3 Jump up ^ Berstel, Jean ; Reutenauer, Christophe ( 1990 ). `` Zeta functions of formal languages ''. Trans. Am. Math. Soc. 321 ( 2 ) : 533 -- 546. CiteSeerX 10.1. 1.309. 3005. Zbl 0797.68092. doi : 10.1090 / s0002 - 9947 - 1990 - 0998123 - x. Jump up ^ Berstel & Reutenauer ( 2011 ) p. 222 Jump up ^ Samuel Eilenberg. Automata, languages, and machines. Academic Press. in two volumes `` A '' ( 1974, ISBN 9780080873749 ) and `` B '' ( 1976, ISBN 9780080873756 ), the latter with two chapters by Bret Tilson. Jump up ^ Straubing, Howard ( 1994 ). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel : Birkhäuser. p. 8. ISBN 3 - 7643 - 3719 - 2. Zbl 0816.68086. Jump up ^ Berstel & Reutenauer ( 2011 ) p. 47 Jump up ^ Sakarovitch, Jacques ( 2009 ). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge : Cambridge University Press. p. 86. ISBN 978 - 0 - 521 - 84425 - 3. Zbl 1188.68177. 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. Sakarovitch, J ( 1987 ). `` Kleene 's theorem revisited ''. Lecture Notes in Computer Science. Lecture Notes in Computer Science. 1987 : 39 -- 50. ISBN 978 - 3 - 540 - 18535 - 2. doi : 10.1007 / 3540185356_29. External links Complexity Zoo : Class REG Automata theory : formal languages and formal grammars Chomsky hierarchy Grammars Languages Abstract machines Type - 0 -- Type - 1 -- -- -- -- -- Type - 2 -- -- Type - 3 -- -- Unrestricted ( no common name ) Context - sensitive Positive range concatenation Indexed -- Linear context - free rewriting systems Tree - adjoining Context - free Deterministic context - free Visibly pushdown Regular -- Non-recursive Recursively enumerable Decidable Context - sensitive Positive range concatenation Indexed -- Linear context - free rewriting language Tree - adjoining Context - free Deterministic context - free Visibly pushdown Regular Star - free Finite Turing machine Decider Linear - bounded PTIME Turing Machine Nested stack Thread automaton restricted Tree stack automaton Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free ( with aperiodic finite monoid ) Acyclic finite Each category of languages, except those marked by a, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line. Retrieved from `` https://en.wikipedia.org/w/index.php?title=Regular_language&oldid=795727747 '' Categories : Formal languages Finite automata Hidden categories : Pages with citations having redundant parameters All articles with unsourced statements Articles with unsourced statements from January 2016 Talk Contents About Wikipedia Languages Čeština Deutsch Ελληνικά Español فارسی Français 한국어 Hrvatski Italiano עברית Magyar Mirandés Nederlands 日本 語 Norsk Polski Português Română Русский Српски / srpski Suomi Українська 中文 Edit links This page was last edited on 16 August 2017, at 02 : 51. Text is available under the Creative Commons Attribution - ShareAlike License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia ® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. About Wikipedia

Question: what is regular language in theory of computation
Answer: a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science