Siguiente: Fundamentos matemáticos Un nivel arriba: Autómatas Anterior: Máquinas de Turing

Jerarquía de Chomsky en autómatas

La complejidad de un autómata está determinada por sus capacidades de transición, de su dispositivo de memoria y las capacidades de inspección en su memoria. De manera natural la jerarquí a gramatical se traduce en una jerarquía equivalente en los autómatas. En la tabla (7) presentamos la equivalente a la mostrada en la tabla (4).

 

Table 7: Jerarquía de Chomsky en autómatas.

Tipo	Nombres	Tipo de autómata reconocedor
0	Irrestricta	Máquinas de Turing
1	Irrestricta con memoria limitada	Máquinas de Turing con cinta acotada
2	Sensibles al contexto con borro	Máquinas de Turing con dominio total
3	Sensibles al contexto no reductivas	Máquinas de Turing con ``espacio lineal''
4	Libres de contexto	Autómatas de pila no-deterministas
5	Libres de contexto deterministas	Autómatas de pila deterministas
6	Lineales	Autómatas lineales
7	Regulares	Autómatas regulares

Siguiente: Fundamentos matemáticos Un nivel arriba: Autómatas Anterior: Máquinas de Turing