Contribuciones Noam Chomsky
(Lenguajes Formales)

Lenguajes libres del contexto

Es una gramática formal en la que cada regla de producción es de la forma: V → w

Derivacion por la izquierda

Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero

Derivacion por la derecha

Si siempre reemplazamos primero el no terminal de más a la derecha.

Lenguajes regulares

Se pueden generar a partir de los lenguajes básicos, con la aplicación de las operaciones de unión, concatenación y * de Kleene un número finito de veces.

Recocido por:

un autómata finito determinista

un autómata finito no determinista

un autómata de pila

un autómata finito alterno

una máquina de Turing de solo lectura

Generado por:

una gramática regular

una gramática de prefijos

Descrito por:

una expresión regular

Lenguajes sensibles al contexto

Es un lenguaje formal que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática la menos frecuente, tanto en la teoría como en la práctica.

Automata Linealmente Acotado

Lenguajes recursivamente enumerables

Es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos.

Si L es un lenguaje regular, entonces L es un lenguaje recursivo

L/P puedo no ser recursivamente enumerable