- 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)
Software and hardware
- 1982: The compilation of regular expressions into integrated
circuits - Robert Floyd, Jeffrey D. Ullman
- 2014: Automata processor
- Closed source hardware ecosystem by Micron
- An efficient and scalable semiconductor architecture for
parallel automata processing (2014) - Dlugosch, Brown, Glendenning,
Leventhal, Noyes
- 2021: Teddy algorithm for regex matching
- From Intel
- Teddy: An efficient SIMD-based literal matching engine for
scalable deep packet inspection - Qiu, Chang, Hong, Zhu, Wang, Li
(ICPP 2021)