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 |