- 1943: Perceptron and DFA
- aka McCulloch-Pitts neuron
- A logical calculus of the ideas immanent to nervous
activity - Warren McCulloch, Walter Pitts
- 1955: Mealy machine
- A method for synthesizing sequential circuits - George
Mealy
- 1956: Chomsky hierarchy
- Three models for the description of language - Noam Chomsky
(1956)
- The algebraic theory of context free languages - Noam
Chomsky, Marcel P. Schützenberger (1963)
- 1956: Moore machine
- Gedanken-experiments on sequential machines - Edward F.
Moore
- 1956: Kleene's theorem
- Representation of events in nerve nets and finite automata
- S. Kleene
- Language accepted by finite automata and regex are same
- Also had Kleene's algorithm for NFA to regex conversion
- 1959: NFA and subset construction for NFA to DFA conversion
- Finite automata and their decision problems - Michael
Rabin, Dana Scott (1959)
- 1960: McNaughton-Yamada NFA construction
- Regular expressions and state graphs for automata
- Regex to DFA conversion
- 1968: Thompson's NFA construction
- Regular expression search algorithm
- Regex to ε-NFA conversion
- Similar to McNaughton-Yamada algorithm ¹
- 1961: Glushkov's NFA construction
- The abstract theory of automata - V. M. Glushkov
(1961)
- Regex to ε-free NFA conversion
- 1964: Brzozowski derivatives
- Derivatives of regular expressions - J. Brzozowski
- Regex to DFA conversion
- 1996: Antimirov derivatives
- Partial derivatives of regular expressions and finite automaton
constructions - V. Antimirov (1996)
- Regex to NFA conversion
- 2003: Follow automata
- Follow automata - Lucian Ilie, Sheng Yu (2003)