Editing Regular language

{{Short description|Formal language that can be expressed using a regular expression}}
{{For|natural language that is regulated|List of language regulators}}
{{Redirect|Kleene's theorem|his theorems for recursive functions|Kleene's recursion theorem}}

In [[theoretical computer science]] and [[formal language theory]], a '''regular language''' (also called a '''rational language''')<ref name="Mitkov2003"/><ref name="Lawson2003"/> 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 [[Regular expression#Patterns for non-regular languages|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'''<ref name="RozenbergSalomaa1997">{{cite book|editor1=Grzegorz Rozenberg |editor2=Arto Salomaa |title=Handbook of Formal Languages: Volume 1. Word, Language, Grammar|chapter-url=https://books.google.com/books?id=yQ59ojndUt4C&pg=PA41|year=1997|publisher=Springer|isbn=978-3-540-60420-4|page=41|author=Sheng Yu|chapter=Regular languages}}</ref> (after American mathematician [[Stephen Cole Kleene]]). In the [[Chomsky hierarchy]], regular languages are the languages generated by [[regular grammar|Type-3 grammars]].

== Formal definition ==
The collection of regular languages over an [[Alphabet (formal languages)|alphabet]] Σ is defined recursively as follows:
* The empty language ∅ is a regular language.
* For each ''a'' ∈ Σ (''a'' belongs to Σ), the [[Singleton (mathematics)|singleton]] language {{mset|''a''}} is a regular language.
* If ''A'' is a regular language, ''A''* ([[Kleene star]]) is a regular language. Due to this, the empty string language {{mset|ε}} is also regular.
* If ''A'' and ''B'' are regular languages, then {{nowrap|''A'' ∪ ''B''}} (union) and {{nowrap|''A'' • ''B''}} (concatenation) are regular languages.
* No other languages over Σ are regular.

See ''{{slink|Regular expression#Formal language theory}}'' for syntax and semantics of regular expressions.

== Examples ==
All finite languages are regular; in particular the [[empty string]] language {{nowrap|1={{mset|ε}} = ∅*}} is regular. Other typical examples include the language consisting of all strings over the alphabet {{mset|''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 {{mset|''a''<sup>''n''</sup>''b''<sup>''n''</sup> | ''n'' ≥ 0}}.<ref>Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).</ref> 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 [[#Location in the Chomsky hierarchy|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)<ref group=note>1. ⇒ 2. by [[Thompson's construction algorithm]]</ref><ref group=note>2. ⇒ 1. by [[Kleene's algorithm]] or using [[Arden's lemma]]</ref>
# it is the language accepted by a [[deterministic finite automaton]] (DFA)<ref group=note>2. ⇒ 3. by the [[powerset construction]]</ref><ref group=note>3. ⇒ 2. since the [[deterministic finite automaton#Formal definition|former definition]] is stronger than the [[nondeterministic finite automaton#Formal definition|latter]]</ref>
# it can be generated by a [[regular grammar]]<ref group=note>2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219</ref><ref group=note>4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218</ref>
# it is the language accepted by an [[alternating finite automaton]]
# it is the language accepted by a [[two-way 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]])<ref>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.</ref>
# it is [[Recognizable set|recognized]] by some finite [[syntactic monoid]] ''M'', meaning it is the [[preimage]] {{mset|''w'' ∈ Σ<sup>*</sup> | ''f''(''w'') ∈ ''S''}} of a subset ''S'' of a finite [[monoid]] ''M'' under a [[monoid homomorphism]] {{nowrap|''f'' : Σ<sup>*</sup> → ''M''}} from the [[free monoid]] on its alphabet<ref group=note>3. ⇔ 10. by the [[Myhill–Nerode theorem]]</ref>
# the number of equivalence classes of its [[syntactic congruence]] is finite.<ref group=note>''u'' ~ ''v'' is defined as: ''uw'' ∈ ''L'' if and only if ''vw'' ∈ ''L'' for all ''w'' ∈ Σ<sup>*</sup></ref><ref group=note>3. ⇔ 11. see the proof in the ''[[Syntactic monoid#Syntactic equivalence|Syntactic monoid]]'' article, and see p. 160 in {{cite book | last=Holcombe | first=W.M.L. | title=Algebraic automata theory | zbl=0489.68046 | series=Cambridge Studies in Advanced Mathematics | volume=1 | publisher=[[Cambridge University Press]] | year=1982 | isbn=0-521-60492-3 }}</ref> (This number equals the number of states of the [[DFA minimization|minimal deterministic finite automaton]] accepting ''L''.)

Properties 10. and 11. are purely algebraic approaches to define regular languages; a similar set of statements can be formulated for a monoid {{nowrap|''M'' ⊆ Σ<sup>*</sup>}}. 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 an 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".<ref name="SedgewickWayne2011">{{cite book|author1=Robert Sedgewick|author2=Kevin Daniel Wayne|title=Algorithms|url=https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA794|year=2011|publisher=Addison-Wesley Professional|isbn=978-0-321-57351-3|page=794}}</ref> Another textbook calls the equivalence of regular expressions and DFAs ("1." and "3." above) "Kleene's theorem".<ref name="AlloucheShallit2003">{{cite book|author1=Jean-Paul Allouche|author2=Jeffrey Shallit|title=Automatic Sequences: Theory, Applications, Generalizations|url=https://books.google.com/books?id=2ZsSUStt96sC&pg=PA129|year=2003|publisher=Cambridge University Press|isbn=978-0-521-82332-6|page=129}}</ref> 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").<ref name="Lawson2003">{{cite book|author=Mark V. Lawson|title=Finite Automata|url=https://books.google.com/books?id=MDQ_K7-z2AMC&pg=PA98|year=2003|publisher=CRC Press|isbn=978-1-58488-255-8|pages=98–103}}</ref><ref name="Rosen2011">{{cite book|author=Kenneth Rosen|title=Discrete Mathematics and Its Applications 7th edition|url=https://books.google.com/books?id=BQQwAgAAQBAJ&pg=PA880|year=2011|publisher=McGraw-Hill Science|pages=873–880}}</ref> 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.<ref name="BunkeSanfeliu1990">{{cite book|author1=Horst Bunke|author2=Alberto Sanfeliu|title=Syntactic and Structural Pattern Recognition: Theory and Applications|url=https://books.google.com/books?id=GfdWeTb5-8QC&pg=PA248|date=January 1990|publisher=World Scientific|isbn=978-9971-5-0566-0|pages=248}}</ref> Other authors simply ''define'' "rational expression" and "regular expressions" as synonymous and do the same with "rational languages" and "regular languages".<ref name="Mitkov2003">{{cite book|author=Ruslan Mitkov|title=The Oxford Handbook of Computational Linguistics|url=https://books.google.com/books?id=yl6AnaKtVAkC&pg=PA754|year=2003|publisher=Oxford University Press|isbn=978-0-19-927634-9|page=754}}</ref><ref name="Lawson2003"/>

Apparently, the term ''regular'' originates from a 1951 technical report where Kleene introduced ''regular events'' and explicitly welcomed "any suggestions as to a more descriptive term".<ref>{{cite report | url=http://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf | author=Stephen Cole Kleene | title=Representation of Events in Nerve Nets and Finite Automata | institution=U.S. Air Force / RAND Corporation | type=Research Memorandum | number=RM-704 | date=Dec 1951 }} Here: p.46</ref> [[Noam Chomsky]], in his 1959 seminal article, used the term ''regular'' in a different meaning at first (referring to what is called ''[[Chomsky normal form]]'' today),<ref name="Chomsky.1959a">{{cite journal | url=http://www.sciencedirect.com/science/article/pii/S0019995859903626/pdf?md5=9d466f851651bd592afa5ee561b7a0b0&pid=1-s2.0-S0019995859903626-main.pdf | author=Noam Chomsky | title=On Certain Formal Properties of Grammars | journal=Information and Control | volume=2 | pages=137&ndash;167 | year=1959 | issue=2 | doi=10.1016/S0019-9958(59)90362-6 | doi-access=free }} Here: Definition 8, p.149</ref> but noticed that his ''finite state languages'' were equivalent to Kleene's ''regular events''.<ref>Chomsky 1959, Footnote 10, p.150</ref>

== Closure properties ==
The regular languages are [[closure (mathematics)|closed]] under various operations, that is, if the languages ''K'' and ''L'' are regular, so is the result of the following operations:
* the [[set-theoretic operations|set-theoretic Boolean operations]]: [[Union (set theory)|union]] {{math|''K'' ∪ ''L''}}, [[intersection (set theory)|intersection]] {{math|''K'' ∩ ''L''}}, and [[complement (set theory)|complement]] {{overline|''L''}}, hence also [[relative complement]] {{math|''K'' &minus; ''L''}}.<ref name=Sal28>Salomaa (1981) p.28</ref>
* the regular operations: {{math|''K'' ∪ ''L''}}, [[concatenation]] {{tmath|K \circ L}}, and [[Kleene star]] {{math|''L''<sup>*</sup>}}.<ref name=Sal27>Salomaa (1981) p.27</ref>
* the [[abstract family of languages|trio]] operations: [[string homomorphism]], inverse string homomorphism, and intersection with regular languages. As a consequence they are closed under arbitrary [[finite state transducer|finite state transductions]], like [[right quotient|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''.<ref>{{cite conference
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston
 | editor1-last = Myers | editor1-first = J. Paul Jr.
 | editor2-last = O'Donnell | editor2-first = Michael J.
 | contribution = Constructivity issues in graph algorithms
 | pages = 150–158
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Constructivity in Computer Science, Summer Symposium, San Antonio, Texas, USA, June 19-22, Proceedings
 | volume = 613
 | year = 1991
 | doi = 10.1007/BFB0021088 | isbn = 978-3-540-55631-2
}}</ref>
* the reverse (or mirror image) ''L''<sup>R</sup>.<ref>Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72</ref> Given a nondeterministic finite automaton to recognize ''L'', an automaton for ''L''<sup>R</sup> can be obtained by reversing all transitions and interchanging starting and finishing states.  This may result in multiple starting states; ε-transitions can be used to join them.

== Decidability properties ==
Given two deterministic finite automata ''A'' and ''B'', it is decidable whether they accept the same language.<ref>Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67</ref>
As a consequence, using the [[#Closure properties|above]] closure properties, the following problems are also decidable for arbitrarily given deterministic finite automata ''A'' and ''B'', with accepted languages ''L''<sub>''A''</sub> and ''L''<sub>''B''</sub>, respectively:<!---avoiding "L(A)" that has not been defined so far, and might be confused with the language variable "L" above--->
* Containment: is ''L''<sub>''A''</sub> ⊆ ''L''<sub>''B''</sub> ?<ref group=note>Check if ''L''<sub>''A''</sub> ∩ ''L''<sub>''B''</sub> = ''L''<sub>''A''</sub>. Deciding this property is [[NP-hard]] in general; see [[:File:RegSubsetNP.pdf]] for an illustration of the proof idea.</ref>
* Disjointness: is ''L''<sub>''A''</sub> ∩ ''L''<sub>''B''</sub> = {{mset}} ?
* Emptiness: is ''L''<sub>''A''</sub> = {{mset}} ?
* Universality: is ''L''<sub>''A''</sub> = Σ<sup>*</sup> ?
* Membership: given ''a'' ∈ Σ<sup>*</sup>, is ''a'' ∈ ''L''<sub>''B''</sub> ?
<!---todo: give complexity for each problem, discuss other formalisms than just DFA--->

For regular expressions, the universality problem is [[NP-complete]] already for a singleton alphabet.<ref>Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401</ref>
For larger alphabets, that problem is [[PSPACE-complete#Regular expressions and automata|PSPACE-complete]].<ref>Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399</ref> If regular expressions are extended to allow also a ''squaring operator'', with "''A''<sup>2</sup>" denoting the same as "''AA''", still just regular languages can be described, but the universality problem has an exponential space lower bound,<ref>Hopcroft, Ullman (1979), Theorem 13.15, p.351</ref><ref>{{cite book | url=https://people.csail.mit.edu/meyer/rsq.pdf |author1=A.R. Meyer  |author2=L.J. Stockmeyer  |name-list-style=amp | title=The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space | publisher=13th Annual IEEE Symp. on Switching and Automata Theory | pages=125–129 | date=Oct 1972 }}</ref><ref>{{cite book | url=https://esp.mit.edu/download/827dcf47cbc9cf4a3b04dbf773ea54fb/M3175_meyer-stockmeyer-word-probs.pdf |author1=L. J. Stockmeyer  |author2=A. R. Meyer |contribution=Word Problems Requiring Exponential Time | title=Proc. 5th ann. symp. on Theory of computing (STOC) | publisher=ACM | pages=1–9 | year=1973 }}</ref> and is in fact complete for exponential space with respect to polynomial-time reduction.<ref>Hopcroft, Ullman (1979), Corollary p.353</ref>

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 equivalence|elementary substructure]] consists precisely of regular languages.  For a binary alphabet, the theory is called [[S2S (mathematics)|S2S]].<ref>{{cite book | last=Weyer | first=Mark | date=2002 | title=Automata, Logics, and Infinite Games |chapter=Decidability of S1S and S2S | series=Lecture Notes in Computer Science | volume=2500 | pages=207–230 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-36387-4_12 | doi=10.1007/3-540-36387-4_12 | publisher=Springer| isbn=978-3-540-00388-5 }}</ref>

== 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 problem]]s that can be solved in constant space (the space used is independent of the input size). '''REGULAR''' ≠ [[AC0|'''AC'''<sup>0</sup>]], 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'''<sup>0</sup>.<ref>{{cite journal | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984| s2cid = 14677270 }}</ref> On the other hand, '''REGULAR''' does not contain '''AC'''<sup>0</sup>, because the nonregular language of [[palindrome]]s, or the nonregular language <math>\{0^n 1^n : n \in \mathbb N\}</math> can both be recognized in '''AC'''<sup>0</sup>.<ref>{{cite book|last1=Cook|first1=Stephen|last2=Nguyen|first2=Phuong|title=Logical foundations of proof complexity|year=2010|publisher=Association for Symbolic Logic|location=Ithaca, NY|isbn=978-0-521-51729-4|pages=75|edition=1. publ.}}</ref>

If a language is ''not'' regular, it requires a machine with at least {{nowrap|[[Big O notation|Ω]](log log ''n'')}} space to recognize (where ''n'' is the input size).<ref>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.</ref> In other words, {{nowrap|DSPACE([[Big O notation|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 <span class="anchor" id="Subclasses"></span> ==
[[Image:Chomsky-hierarchy.svg|thumb|250px|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 language|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 is not regular, one often uses the [[Myhill–Nerode theorem]] and the [[Pumping lemma for regular languages|pumping lemma]]. Other approaches include using the [[Regular language#Closure properties|closure properties]] of regular languages<ref>{{cite web|title=How to prove that a language is not regular?|url=https://cs.stackexchange.com/q/1031|access-date=10 April 2018|website=cs.stackexchange.com}}</ref> or quantifying [[Kolmogorov complexity]].<ref>{{Cite book|last=Hromkovič|first=Juraj|url=https://www.worldcat.org/oclc/53007120|title=Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography|date=2004|publisher=Springer|isbn=3-540-14015-8|pages=76–77|oclc=53007120}}</ref>

Important subclasses of regular languages include:
* Finite languages, those containing only a finite number of words.<ref>A finite language should not be confused with a (usually infinite) language generated by a finite automaton.</ref> These are regular languages, as one can create a [[regular expression]] that is the [[Union (set theory)|union]] of every word in the language.
* [[Star-free language]]s, 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 [[Complement (set theory)|complementation]] but not the [[Kleene star]]: this class includes all finite languages.<ref>{{cite book|editor1=Jörg Flum |editor2=Erich Grädel |editor3=Thomas Wilke |title=Logic and automata: history and perspectives|year=2008|publisher=Amsterdam University Press|isbn=978-90-5356-576-6|chapter-url=http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf|chapter=First-order definable languages|author1=Volker Diekert |author2=Paul Gastin }}</ref>

== Number of words in a regular language ==
Let <math>s_L(n)</math> denote the number of words of length <math>n</math> in <math>L</math>.  The [[ordinary generating function]] for ''L'' is the [[formal power series]]
: <math>S_L(z) = \sum_{n \ge 0} s_L(n) z^n \ . </math>

The generating function of a language ''L'' is a [[rational function]] if ''L'' is regular.<ref name=Honkala>{{cite journal | zbl=0675.68034 | last=Honkala | first=Juha | title=A necessary condition for the rationality of the zeta function of a regular language | journal=Theor. Comput. Sci. | volume=66 | issue=3 | pages=341–347 | year=1989 | doi=10.1016/0304-3975(89)90159-x | doi-access=free }}</ref>  Hence for every regular language <math>L</math> the sequence <math>s_L(n)_{n \geq 0}</math> is [[constant-recursive sequence|constant-recursive]]; that is, there exist an [[integer]] constant <math>n_0</math>, [[complex number|complex]] constants <math>\lambda_1,\,\ldots,\,\lambda_k</math> and complex [[polynomial]]s <math>p_1(x),\,\ldots,\,p_k(x)</math> such that for every <math>n \geq n_0</math> the number <math>s_L(n)</math> of words of length <math>n</math> in <math>L</math> is <math>s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n</math>.<ref>Flajolet & Sedgweick, section V.3.1, equation (13).</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1048 |title=Number of words in the regular language $(00)^*$|website=cs.stackexchange.com|access-date=10 April 2018}}</ref><ref>{{cite web| url = https://cs.stackexchange.com/q/11333| title = Proof of theorem for arbitrary DFAs}}</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1045 |title=Number of words of a given length in a regular language|website=cs.stackexchange.com|access-date=10 April 2018}}</ref>

Thus, non-regularity of certain languages <math>L'</math> can be proved by counting the words of a given length in
<math>L'</math>. Consider, for example, the [[Dyck language]] of strings of balanced parentheses. The number of words of length <math>2n</math>
in the Dyck language is equal to the [[Catalan number]] <math>C_n\sim\frac{4^n}{n^{3/2}\sqrt{\pi}}</math>, which is not of the form <math>p(n)\lambda^n</math>,
witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvalues <math>\lambda_i</math> could have the same magnitude. For example, the number of words of length <math>n</math> in the language of all even binary words is not of the form <math>p(n)\lambda^n</math>, but the number of words of even or odd length are of this form; the corresponding eigenvalues are <math>2,-2</math>. In general, for every regular language there exists a constant <math>d</math> such that for all <math>a</math>, the number of words of length <math>dm+a</math> is asymptotically <math>C_a m^{p_a} \lambda_a^m</math>.<ref>Flajolet & Sedgewick (2002) Theorem V.3</ref>

The ''zeta function'' of a language ''L'' is<ref name=Honkala/>
: <math>\zeta_L(z) = \exp \left({ \sum_{n \ge 0} s_L(n) \frac{z^n}{n} }\right) . </math>

The zeta function of a regular language is not in general rational, but that of an arbitrary [[cyclic language]] is.<ref>{{cite journal | zbl=0797.68092 | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Zeta functions of formal languages | journal=Trans. Am. Math. Soc. | volume=321 | number=2 | pages=533–546 | year=1990 | doi=10.1090/s0002-9947-1990-0998123-x| citeseerx=10.1.1.309.3005 }}</ref><ref>Berstel & Reutenauer (2011) p.222</ref>

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

[[Rational set]] generalizes the notion (of regular/rational language) to monoids that are not necessarily [[free monoid|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 [[Samuel Eilenberg|Eilenberg]]'s monograph<ref name="Eilenberg1974">{{cite book|author=Samuel Eilenberg|title=Automata, languages, and machines|publisher=Academic Press}} in two volumes "A" (1974, {{isbn|9780080873749}}) and "B" (1976, {{isbn|9780080873756}}), the latter with two chapters by Bret Tilson.</ref> 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.”<ref>{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | url=https://archive.org/details/finiteautomatafo0000stra | url-access=registration | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page= [https://archive.org/details/finiteautomatafo0000stra/page/8 8] }}</ref>

[[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 expression]]s and [[weighted automata]]. In this algebraic context, the regular languages (corresponding to [[Boolean semiring|Boolean]]-weighted rational expressions) are usually called ''rational languages''.<ref>Berstel & Reutenauer (2011) p.47</ref><ref>{{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 | page = 86 }}</ref> Also in this context, Kleene's theorem finds a generalization called the [[Kleene–Schützenberger theorem]].

== Learning from examples ==
{{main|Induction of regular languages}}

== Notes ==
{{reflist|group=note}}

== References ==
{{refbegin}}
* {{cite book | last1=Berstel | first1=Jean | author-link1=Jean Berstel | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications
  | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]]
  | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }}
* {{cite book |last1=Eilenberg |first1=Samuel |author-link1=Samuel Eilenberg |title=Automata, Languages, and Machines. Volume A
  |series=Pure and Applied Mathematics |volume=58 |year=1974 |publisher=Academic Press |location=New York |zbl=0317.94045 }}
* {{cite book | first=Arto | last=Salomaa | author-link=Arto Salomaa | title=Jewels of Formal Language Theory | publisher=Pitman Publishing
  | isbn=0-273-08522-0 | year=1981 | zbl=0487.68064 }}
* {{cite book | first=Michael | last=Sipser | author-link = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation
  | publisher = PWS Publishing | isbn = 0-534-94728-X | zbl=1169.68300 | title-link=Introduction to the Theory of Computation }} Chapter 1: Regular Languages, pp.&nbsp;31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.&nbsp;152–155.
* Philippe Flajolet and Robert Sedgewick, ''[[Analytic Combinatorics]]'': Symbolic Combinatorics.  Online book, 2002.
* {{cite book|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X|title-link=Introduction to Automata Theory, Languages, and Computation }}
* {{cite book | author=Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman | title=The Design and Analysis of Computer Algorithms | url=https://archive.org/details/designanalysisof00ahoarich | url-access=registration | publisher=Addison-Wesley | year=1974 | isbn=9780201000290 }}

{{refend}}
{{reflist}}

== Further reading ==
* [[Stephen Cole Kleene|Kleene, S.C.]]: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp.&nbsp;3–41. Princeton University Press, Princeton (1956); it is a slightly modified version of his 1951 [[RAND Corporation]] report of the same title, [http://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf RM704].
* {{cite book | last1 = Sakarovitch | first1 = J | title = Trends, Techniques, and Problems in Theoretical Computer Science | year = 1987| chapter = Kleene's theorem revisited | volume = 1987 | pages = 39–50 | doi = 10.1007/3540185356_29 | series = Lecture Notes in Computer Science | isbn = 978-3-540-18535-2 }}

== External links ==
* {{CZoo|Class REG|R#reg}}

{{Formal languages and grammars}}

[[Category:Formal languages]]
[[Category:Finite-state machines]]