Alvarado - Contribuciones Noam Chomsky

Mais informações

Estructuralimso

por Leonor Silva

COMUNICACIÓN MEDIATICA

por Neiby Jilena Hidalgo Plaza

Lenguajes, niveles y máquinas virtuales Final?

por RAMIREZ SANTOS RAMIREZ SANTOS

Comunicar:Es una actividad de doble vía: por un lado, hay alguien que quiere hacer saber algo y, por el otro, hay alguien que procura entender lo que ese otro le quiere decir. El primero es la instancia productora, a la que también se denomina sujeto productor; el segundo es la instancia que reconoce e interpreta, que puede nombrarse como sujeto interpretador.

por Gabriel Alberto Diele

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