Lenguajes Formales

Guión Técnico

Audio

¿Qué es un lenguaje formal?

Lenguaje (axioma, terminales, no terminales, reglas de producción).

Un conjunto de símbolos no terminales {A, B, C, … S}

Un conjunto de símbolos terminales {a, b, c, …}

Un símbolo no terminal, llamado axioma S

Un conjunto de reglas de producción de la forma A := α

Definición general:

La teoría de lenguajes formales es la aproximación matemática que intenta describir los aspectos fundamentales del lenguaje. La primera definición importante es la de (alfabeto), que podemos entenderla como un conjunto que contiene una cantidad finita de símbolos.

Una (proposición) es una cadena finita de símbolos del alfabeto. Hay infinitamente tantas proposiciones como enteros, i.e. el conjunto de las proposiciones es numerable.

Un (lenguaje) es un conjunto de proposiciones. De entre todas las posibles proposiciones, hay unas que pertenecen al lenguaje y otras que no. Esto lo determina la (gramática) que es la lista finita de reglas que determinan un lenguaje.

Y puede ser vista de hecho, como (reglas de producción). Además, las proposiciones pueden incluir (elementos terminales) y (elementos no terminales). Los elementos terminales son elementos del alfabeto. Los no terminales son huecos, en los que se pueden ir colocando nuevas preposiciones.

1.2 Algo de teoria de la computacion

PD: prof. en este link viene el punto 1.2 pero no se si le parezca realmente importante. http://www.fenomec.unam.mx/pablo/seminario/Lenguajes.pdf

1.3. La jerarquía de Chomsky

En 1956, el lingüista Noam Chomsky da una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. La Jerarquía de Chomsky consta de cuatro niveles:

·         Gramáticas de tipo 0 (sin restricciones), que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga. No tienen restricciones. Pueden representar cualquier cadena finita de símbolos terminales o no terminales.

·         Gramáticas de tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto. Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing no determinista cuya cinta de memoria esta acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como Autómatas Linealmente Acotados.

·         Gramáticas de tipo 2 (gramáticas libres del contexto) generan los lenguajes independientes del contexto. Estos lenguajes son aquellos que pueden ser reconocidos por un autómata con pila dentro de la teoría de la computación.

·         Gramáticas de tipo 3 (gramáticas regulares) generan los lenguajes regulares. Estas gramáticas se restringen a aquellas reglas que tienen en la parte izquierda un elemento no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal. Estos lenguajes son aquellos que en teoría de la computación pueden ser aceptados por un autómata finito. Esta familia de lenguajes pueden ser, también, obtenidas por medio de expresiones regulares.

Es posible demostrar que una gramática sensible al contexto no es equivalente a una gramática libre de contexto, y que ambas, las gramáticas sensibles al contexto y libres de contexto no son equivalentes a las gramáticas regulares. Lo primero, a través del lema de bombeo para gramáticas libres de contexto; y análogamente para el segundo con el lema de bombeo para gramáticas regulares.

PD: en este link en la viene sobre lenguajes formales, aunque yo en lo personal no le entendí.

http://www.profesores.frc.utn.edu.ar/sistemas/ssl/marciszack/GHD/T-Gramaticas.htm

¿Qué es una gramática generativa libre de contexto?

Para Chomsky la competencia es el conjunto de reglas subyacentes a las infinitas oraciones de una lengua.

Los semánticos generativos trataban de explicar por medio de transformaciones ciertas relaciones semánticas que no están expresadas formalmente en la gramática (por ejemplo, las que vinculan en español los verbos morir y matar –entendido como ‘causar que otro muera’); por el contrario, Chomsky intentó demostrar que esas relaciones no pueden ser resultado de operaciones sintácticas sino que deben ser expresadas por medio de reglas de otra naturaleza (léxicas o semánticas).

Otros pares de oraciones relacionadas entre sí que, para Chomsky, pueden ser explicados por medio de transformaciones son las oraciones marcadas por la polaridad afirmativa/negativa (por ejemplo, la serie Juan fue al cine / Juan no fue al cine / Juan sí fue al cine) o el contraste entre la voz activa y la pasiva (Juan destruyó los diques / Los diques fueron destruidos por Juan). Por su parte, también la morfología verbal (por ejemplo, la concordancia entre verbo y sujeto) es introducida por medio de transformaciones. Nótese que, mientras algunas transformaciones son obligatorias (la concordancia de verbo y sujeto, por ejemplo), otras son optativas (la pasiva o la negación).

De modo que podríamos establecer la siguiente proporción:

Lengua =  Competencia

Inventario de elementos - sistema de reglas

Así, dada la proporción;

Dionisos=  Ares

Copa- Escudo

se puede despejar uno de los términos y decir que la copa es «el escudo de Dionisos», o bien, que el escudo es «la copa de Ares», procedimiento éste mediante el cual se transfiere a un objeto el nombre que designa otro objeto (figura metafórica).

¿Qué es inferencia gramatical? 

La inferencia gramatical es un conjunto de reglas innatas que permite traducir combinaciones de ideas a combinaciones de palabras. Chomsky fundamentó que la gramática es un sistema combinatorio discreto que permite construir infinitas frases a partir de un número finito de elementos mediante reglas diversas que pueden formalizarse. La nueva teoría consideraba que las expresiones tienen una sintaxis que puede ser caracterizada globalmente por una gramática formal; en particular, una gramática extendida por normas de transformación. Se les supone a los niños un conocimiento innato de la gramática elemental común a todas las lenguas humanas. Se sostiene que la modelización del conocimiento de la lengua a través de una gramática formal explica la "productividad" de la lengua: con un juego reducido de reglas gramaticales y un conjunto finito de términos, los humanos pueden producir un número infinito de frases, incluidas frases que nadie haya dicho anteriormente.

La utilización en la práctica de los métodos sintácticos de reconocimiento de formas viene condicionada, es decir, es necesario conocer la gramática. Como generalmente ello no es posible a priori, se hace necesario construirla u obtenerla mediante algún método de aprendizaje, y dado que en la mayoría de los problemas de reconocimiento de formas la única información de que se dispone sobre la forma se halla resumida en un conjunto de ejemplos, se recurre usualmente a métodos de aprendizaje inductivo, que en el caso de los métodos sintácticos se engloban en lo que se conoce como inferencia gramatical.

La inferencia gramatical se especifica mediante la definición de:

a)      Un dominio de formas a inferir.

b)      Un espacio de hipótesis o representaciones.

c)       Un método de presentación de ejemplos.

d)      Un método de inferencia.

e)      Un criterio de éxito.

Usualmente las aplicaciones prácticas se centran en métodos constructivos, los cuales utilizan normalmente sólo muestras positivas. La gran mayoría de los métodos de inferencia gramatical existentes en la actualidad son métodos  heurísticos e infieren gramáticas regulares.

El espacio de las hipótesis depende del dominio de formas que debe de inferir el sistema y de la representación utilizada. Como única condición, debe de estar compuesto de por lo menos una representación para cada forma del dominio.

En general en inferencia inductiva se utilizan dos métodos de presentación de ejemplos:

·         Presentación positiva del lenguaje L: es una sucesión de elementos de (muestras positivas). Solo texto y los ejemplos aparecen en un orden particular, es decir de pertenencia.

·         Presentación completa del lenguaje L: es una sucesión de elementos y de su complementario (muestras positivas y muestras negativas), marcados para indicar su pertenencia o no a L. Los ejemplos aparecen en un orden arbitrario, es decir de equivalencia

La gran mayoría de los métodos prácticos de inferencia gramatical son constructivos y utilizan únicamente presentación positiva. A su vez, de entre todos ellos, la gran mayoría está orientada a la inferencia de lenguajes regulares, siendo escasos los que infieren gramáticas de contexto libre o superiores.

De entre los métodos de inferencia de gramáticas regulares (autómatas) cabe destacar los que se basan en distintos métodos de agrupar los estados del autómata árbol receptor de prefijos de las muestras positivas. Este autómata proporciona un espacio de búsqueda muy adecuado, siempre que la muestra sea estructuralmente completa.

http://www.dlsi.ua.es/asignaturas/acei/Datos/7.1-f.pdf

http://www.uv.es/hmr/Tesis/PDF/Cap3.pdf

Video