• Author / Uploaded
• Ronald Torrecilla

Citation preview

República Bolivariana de Venezuela Ministerio Del Poder Popular para la Educación Universitaria, Ciencia y Tecnología Universidad Dr. José Gregorio Hernández Facultad de Ingeniería Maracaibo Estado Zulia

TEORIA DE LA COMPUTACION

Realizado Por: Ronald Torrecilla C.I. V-18.987.304 GRUPO # 2

INTRODUCCIÓN

Para gramáticas sensibles al contexto, el problema de decidir si el lenguaje que genera es vacío o no también es un problema indecidible. Los lenguajes libres de contexto tienen una aplicación a los compiladores, aunque existen otras aplicaciones como la compartición de información. Según Chomsky, los tipos de lenguajes formales pueden dividirse en tres: de estados finitos (o regulares), de estructura de frase (o libres de contexto) y transformacionales (o sensibles al contexto). Tal clasificación es conocida como la jerarquía de Chomsky (JCh). El principal objetivo de Chomsky (1956) y su jerarquía era demostrar que los dos primeros tipos de gramáticas son incapaces de dar cuenta, de manera simple y general, de la complejidad de las lenguas naturales. En particular, Chomsky demostró que el inglés presenta propiedades que no pueden ser reflejadas ni por gramáticas de estados finitos ni por gramáticas de estructura de frase.

ESQUEMA

1. 2. 3. 4. 5.

Lenguaje Sensible de Contexto Aplicaciones clásica problema de la parada Problema insolubles algorítmicamente Técnicas de Análisis Léxico Técnicas de Análisis Sintáctico

DESARROLLO

1. Lenguaje Sensible de Contexto Este tipo de lenguajes son definidos por las gramáticas sensibles del contexto, dichas gramáticas definen esta clase intermedia de lenguajes, que se sitúan entre los lenguajes libres de contexto y los lenguajes recursivos. Casi cualquier lenguaje que uno pueda concebir es sensible al contexto, a excepción de los lenguajes recursivos Las reglas son de la forma α → β, donde α y β no permiten ε de una producción, i.e., no se permite la palabra vacía tanto para el lado izquierdo como para el lado derecho. Sin embargo, pueden contener cualquier cantidad de variables (no terminales) y constantes (terminales). Las gramáticas sensitivas del contexto son estrictamente más poderosas que las gramáticas libres del contexto; un ejemplo es el lenguaje de las cadenas de la forma {a n b n c n}, para el que no hay ninguna gramática libre de contexto (GLC). El concepto de la gramática sensible al contexto fue introducido cerca Noam Chomsky en los años 50 como manera de describir el sintaxis de lengua natural donde está de hecho a menudo el caso que una palabra puede o no puede ser apropiada en cierto lugar dependiendo del contexto. A lenguaje formal eso se puede describir por una gramática sensible al contexto se llama a lengua sensible al contexto. Son las que generan los lenguajes sensibles al contexto. Los lenguajes sensibles al contexto son aquellos que pueden ser reconocidos por las Autómatas Linealmente Acotados ALA. En forma general toda gramática se define mediante una cuádrupla G=(N,T, P,S), siendo -N es un conjunto finito de símbolos no terminales -T es un conjunto finito de símbolos terminales N∩ T=∅ -P es un conjunto finito de reglas de producción -S Símbolo distinguido o Axioma S∉ (N∪ T).

2. Aplicaciones clásica problema de la parada

El problema de la parada o problema de la detención (halting problem en inglés) para máquinas de Turing consiste en: dada una MT M y una palabra w, determinar si M terminará en un número finito de pasos cuando se ejecuta usando w como entrada. Alan Turing, en su famoso artículo “On computable numbers, with an application to the Entscheidungs problem” (1936), demostró que el problema de la parada de la máquina de Turing es indecidible, en el sentido de que ninguna máquina de Turing lo puede resolver. 3. Problema insolubles algorítmicamente Un problema de decisión (PD) es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Problemas de decisión. Un problema de decisión es Soluble si existe un algoritmo total para determinar si la propiedad es verdadera (Existe una MT que siempre para al resolver el problema). Parcialmente soluble si existe un algoritmo parcial para determinar si la propiedad es verdadera (existe una MT que resuelve el problema, pero puede no parar). Insoluble si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una MT), Ejemplos de problemas de decisión: ¿Existe un algoritmo para decidir si un número natural cualquiera es par? Si es soluble. ¿Existe un algoritmo para decidir si dos autómatas finitos cualesquiera son equivalentes? Si es un problema soluble.

¿Existe un algoritmo para determinar si una gramática es ambigua o no? No es insoluble. Muchos problemas insolubles son paradójicos en su naturaleza. Ej: la paradoja de Russell. Un peluquero afecta a todas las personas que no se afectan a si mismas. El peluquero: ¿se afeita así mismo? (insoluble). 4. Técnicas de Análisis Léxico El analizador léxico es la primera fase de un compilador. Su principal función consiste en leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos que utiliza el analizador sintáctico para hacer el análisis. Como el analizador léxico es la parte del compilador que lee el texto fuente, también puede realizar ciertas funciones secundarias en la interfaz del usuario, como eliminar del programa fuente comentarios y espacios en blanco en forma de caracteres de espacio en blanco, caracteres TAB y de línea nueva. Otra función es relacionar los mensajes de error del compilador con el programa fuente. Esta etapa está basada usualmente en una máquina de estados finitos. Esta máquina contiene la información de las posibles secuencias de caracteres que puede conformar cualquier token que sea parte del lenguaje (las instancias individuales de estas secuencias de caracteres son denominados lexemas). Por ejemplo, un token de naturaleza entero puede contener cualquier secuencia de caracteres numéricos. Hay varias razones para dividir la fase de análisis de la compilación en análisis léxico y análisis sintáctico. Un diseño sencillo es quizá la consideración más importante. Separar el análisis léxico del análisis sintáctico a menudo permite simplificar una u otra de dichas fases.

Se mejora la eficiencia del compilador. Un analizador léxico independiente permite construir un procesador especializado y potencialmente más eficiente para esta función. Gran parte de tiempo se consume en leer el programa fuente y dividirlo en componentes léxicos. Con técnicas especializadas de manejo de buffer para la lectura de caracteres de entrada y procesamiento de componentes léxicos se puede mejorar significativamente el rendimiento de un compilador. Se mejora la transportabilidad del compilador. Las peculiaridades del alfabeto de entrada y otras anomalías propias de los dispositivos pueden limitarse al analizador léxico. 5. Técnicas de Análisis Sintáctico Es el análisis de las funciones sintácticas o relaciones de concordancia y jerarquía

que

guardan

las palabras agrupándose

entre

sí

en sintagmas, oraciones simples y compuestas de proposiciones o nexos. Como no está muchas veces claro el límite entre la sintaxis y la morfología a estos respectos, especialmente según el tipo de lengua de que se trate, también se suele denominar análisis morfosintáctico, aunque esta denominación se suele reservar para un análisis más profundo y detenido.

CONCLUSION En este trabajo he explorado la relación entre la jerarquía de Chomsky, he expuesto cómo es posible implementar la idea de que el cambio lingüístico se

manifiesta de manera progresiva en los diversos estratos de la gramática, en términos diacrónicos. Este planteamiento no es incompatible con el supuesto de que la adquisición y la evolución del lenguaje son, en sus aspectos fundamentales, espontáneas y, al mismo tiempo, nos permite reflejar de una manera plausible cómo tiene lugar el cambio lingüístico.

BIBLIOGRAFIA https://teoriacomputacion.wordpress.com/2014/04/30/maquina-de-turing/ http://www.sc.ehu.es/jiwnagom/MAC1-ALF/MAC-archivos/Tema3.pdf http://uncomp.uwe.ac.uk/genaro/Papers/Veranos_McIntosh_files/lenguajesNivardo AMC2011.pdf http://lorien.die.upm.es/juancho/pfcs/DPF/capitulo2.pdf