next up previous contents
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


next up previous contents
Siguiente: Fundamentos matemáticos Un nivel arriba: Autómatas Anterior: Máquinas de Turing
Guillermo Morales-Luna
2000-06-27