En 1958 Chomsky y Miller notaron que las gramáticas de tipo 3 son equivalentes a los autómatas finitos introducidos por Kleene en 1951.Chomsky y Schutzenberger en 1963 demostraron que las gramáticas de tipo 2 equivalen a los autómatas con pila.
Por último, en 1964 Kuroda descubre que los lenguajes de tipo 1 son reconocidos por los autómatas linealmente acotados.
Los autómatas linealmente acotados son similares a una máquina de Turing, sabemos que esta última tiene una cinta infinita.
Los autómatas linealmente acotados se basan en la gramática de Tipo 1 (sensibles al contexto).
Así cualquier cálculo real hecho en una computadora no es tan extenso como lo que podría completarse en una máquina de Turing.