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