Jerarquía de Chomsky

Existen cuatro tipos importantes de gramáticas, las cuales fueron definidas por Chomsky en [CN65], de acuerdo a la forma de sus producciones. Según Chomsky a cada uno los lenguajes producidos por cada una de éstas gramáticas le corresponde un tipo de autómata que reconozca dicho lenguaje, las correspondecias son las siguientes: