Editing Automata theory (section)

==History==
The theory of abstract automata was developed in the mid-20th century in connection with [[finite automata]].<ref>{{cite web | url=http://www.rutherfordjournal.org/article030107.html | title=The Structures of Computation and the Mathematical Structure of Nature | first=Michael S. | last=Mahoney | publisher=The Rutherford Journal | access-date=7 June 2020 }}</ref> Automata theory was initially considered a branch of mathematical [[systems theory]], studying the behavior of discrete-parameter systems. Early work in automata theory differed from previous work on systems by using [[abstract algebra]] to describe [[information system]]s rather than [[differential calculus]] to describe material systems.<ref>{{cite book
 |last=Booth
 |first=Taylor
 |date=1967
 |title=Sequential Machines and Automata Theory
 |location= New York
 |publisher= John Wiley & Sons
 |page= 1-13
 |isbn= 0-471-08848-X
}}</ref> The theory of the [[finite-state transducer]] was developed under different names by different research communities.<ref>{{cite journal
 |last1        = Ashby
 |first1       = William Ross
 |date         = January 15, 1967
 |title        = The Place of the Brain in the Natural World
 |url          = http://www.rossashby.info/Ashby-Mechanisms_of_intelligence.pdf#16
 |journal      = Currents in Modern Biology
 |volume       = 1
 |issue        = 2
 |pages        = 95–104
 |doi          = 10.1016/0303-2647(67)90021-4
 |pmid         = 6060865
 |bibcode = 1967BiSys...1...95A
 |access-date  = 2021-03-29 
 |archive-date = 2023-06-04 
 |archive-url  = https://web.archive.org/web/20230604002636/http://rossashby.info/Ashby-Mechanisms_of_intelligence.pdf#16
 |url-status   = dead
}}: "The theories, now well developed, of the "finite-state machine" (Gill, 1962), of the "noiseless transducer" (Shannon and Weaver, 1949), of the "state-determined system" (Ashby, 1952), and of the "sequential circuit", are essentially homologous."</ref> The earlier concept of [[Turing machine]] was also included in the discipline along with new forms of infinite-state automata, such as [[pushdown automata]].

1956 saw the publication of ''Automata Studies'', which collected work by scientists including [[Claude Shannon]], [[W. Ross Ashby]], [[John von Neumann]], [[Marvin Minsky]], [[Edward F. Moore]], and [[Stephen Cole Kleene]].<ref>{{cite book
 |last=Ashby
 |first=W. R.
 |display-authors=etal
 |editor1=C.E. Shannon
 |editor2=J. McCarthy
 |date=1956
 |title=Automata Studies
 |location= Princeton, N.J.
 |publisher= Princeton University Press
}}</ref> With the publication of this volume, "automata theory emerged as a relatively autonomous discipline".<ref name="Arbib 1969"/> The book included Kleene's description of the set of regular events, or [[regular languages]], and a relatively stable measure of complexity in Turing machine programs by Shannon.<ref>{{cite book
 |last1=Li
 |first1=Ming
 |first2=Vitanyi
 |last2=Paul
 |date=1997
 |title=An Introduction to Kolmogorov Complexity and its Applications
 |location= New York
 |publisher= Springer-Verlag
 |page=84
}}</ref> 
In the same year, [[Noam Chomsky]] described the [[Chomsky hierarchy]], a correspondence between automata and [[formal grammars]],<ref>{{cite journal |last=Chomsky |first=Noam |author-link=Noam Chomsky |date=1956 |title=Three models for the description of language |doi=10.1109/TIT.1956.1056813 |journal=IRE Transactions on Information Theory |volume=2 |issue=3 |pages=113–124 |s2cid=19519474 |url=https://chomsky.info/wp-content/uploads/195609-.pdf |archive-url=https://web.archive.org/web/20160307035549/https://chomsky.info/wp-content/uploads/195609-.pdf |archive-date=2016-03-07 |url-status=live }}</ref> and Ross Ashby published ''[[An Introduction to Cybernetics]]'', an accessible textbook explaining automata and information using basic [[set theory]].

The study of [[linear bounded automata]] led to the [[Myhill–Nerode theorem]],<ref>{{cite journal
| last1      = Nerode
| first1     = A.
|author1-link = Anil Nerode
| date       = 1958
| title      = Linear Automaton Transformations
| journal = Proceedings of the American Mathematical Society
| volume = 9
| issue = 4
| page = 541
| doi = 10.1090/S0002-9939-1958-0135681-9
| url        = https://www.ams.org/journals/proc/1958-009-04/S0002-9939-1958-0135681-9/
| doi-access = free
}}</ref> which gives a necessary and sufficient condition for a formal language to be regular, and an exact count of the number of states in a minimal machine for the language. The [[pumping lemma for regular languages]], also useful in regularity proofs, was proven in this period by [[Michael O. Rabin]] and [[Dana Scott]], along with the computational equivalence of deterministic and nondeterministic finite automata.<ref>{{cite journal|last1=Rabin |first1=Michael |author-link1=Michael O. Rabin|last2=Scott |first2=Dana |author-link2=Dana Scott  |date=Apr 1959 |title=Finite Automata and Their Decision Problems |journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |url=http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |doi=10.1147/rd.32.0114 |url-status=unfit |archive-url=https://web.archive.org/web/20101214122150/http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |archive-date=December 14, 2010 }}</ref> 

In the 1960s, a body of algebraic results known as "structure theory" or "algebraic decomposition theory" emerged, which dealt with the realization of sequential machines from smaller machines by interconnection.<ref name="structure theory">{{cite book
 |last1=Hartmanis
 |first1=J.
|author1-link = Juris Hartmanis
 |last2=Stearns
 |first2=R.E.
|author2-link = Richard E. Stearns
 |date=1966
 |title=Algebraic Structure Theory of Sequential Machines
 |location=Englewood Cliffs, N.J.
 |publisher=Prentice-Hall
}}</ref> While any finite automaton can be simulated using a [[functional completeness | universal gate set]], this requires that the simulating circuit contain loops of arbitrary complexity. Structure theory deals with the "loop-free" realizability of machines.<ref name="Arbib 1969"/>
The theory of [[computational complexity]] also took shape in the 1960s.<ref>{{cite web
| last1      = Hartmanis
| first1     = J.
| last2      = Stearns
| first2     = R. E.
| date       = 1964
| title      = Computational complexity of recursive sequences
| url        = http://www.cs.albany.edu/~res/complexity_recursive_seq_1964.pdf
}}</ref><ref>{{cite web
| last1      = Fortnow
| first1     = Lance
| last2      = Homer
| first2     = Steve
| date       = 2002
| title      = A Short History of Computational Complexity
| url        = https://people.cs.uchicago.edu/~fortnow/papers/history.pdf
}}</ref> By the end of the decade, automata theory came to be seen as "the pure mathematics of computer science".<ref name="Arbib 1969">{{cite book
 |last=Arbib
 |first=Michael
 |date=1969
 |title=Theories of Abstract Automata
 |location= Englewood Cliffs, N.J.
 |publisher= Prentice-Hall
}}</ref>