Tipo de lenguaje aceptado

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 \)
comments powered by Disqus