Alvarado - Contribuciones Noam Chomsky

Mer av detta

Orígenes de la IA

av Mariangel Torres

Programación lineal

av Cristian Hernandez

Proyecto Trimestral

av Carlos Gomez

Noam shomsky

av luz Marina Guevara Rincon

Contribuciones Noam Chomsky (Lenguajes Formales)

Jeraquia de Chomsky

Es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.

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.

L/P puedo no ser recursivamente enumerable

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

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 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.

Descrito por:

una expresión regular

Generado por:

una gramática regular

una gramática de prefijos

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

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 derecha

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

Derivacion por la izquierda

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