Alvarado - Contribuciones Noam Chomsky

Plus de détails

software testing

par jefferson sanabria

La morfología. Formación de palabras. Palabras derivadas y compuestas

par Mariajose Fortunato

SOFTWARE DE PROGRAMACION

par fredy andres

teoeria de automatas

par ANTONIO GARCIA

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