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.