Hasta este momento hemos visto el formalismo de las MT, sus equivalencias y el lenguaje que acepta una MT esecífica. Sin embargo, no hemos visto el tipo de lenguaje que acepta, al tipo de lenguaje que acepta una MT se le conoce como recursivo. Por el momento lo que sabemos es este tipo de lenguajes contiene a los lenguajes sensibles dependientes del contexto, pero contiene lenguajes que no lo son.
Lenguaje | Gramática | Máquina | Ejemplo |
---|---|---|---|
Recursivos | \( \alpha \rightarrow \beta \) | MT, ADP, MTₖ, … | ?? |
Lenguaje Dependientes del Contexto | \( \gamma A \beta \rightarrow \gamma \alpha \beta \) | Autómata Lineal con Frontera | \( a^nb^nc^n \) |
Lenguaje Independiente del Contexto | \( A \rightarrow \alpha \) | Autómata de Pila | \( a^nb^n \) |
Lenguaje Regular | \( A \rightarrow bC | d \) | AF, AFND y AFND-ε | \( a^n \) |