Editing Regular language (section)

== 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>