Lenguaje Formal

Lenguaje formal

En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.

Informalmente, el término lenguaje formal se utiliza en muchos contextos (en las ciencias, en derecho, etc.) para referirse a un modo de expresión más cuidadoso y preciso que el habla cotidiana. Hasta finales de la década de 1990, el consenso general era que un lenguaje formal, en el sentido que trata este artículo, era en cierto modo la versión «límite» de este uso antes mencionado: un lenguaje tan formalizado que podía ser usado en forma escrita para describir métodos computacionales. Sin embargo, hoy en día, el punto de vista de que la naturaleza esencial de los lenguajes naturales (sin importar su grado de «formalidad» en el sentido informal antes descrito) difiere de manera importante de aquella de los verdaderos lenguajes formales (en el sentido estricto de este artículo) gana cada vez más adeptos.

Gramática formal

La gramática es un ente o modelo matemático que permite especificar un lenguaje, es decir, es el conjunto de reglas capaces de generar todas las posibilidades combinatorias de ese lenguaje, ya sea éste un lenguaje formal o un lenguaje natural.

La expresión «gramática formal» tiene dos sentidos:

(a) gramática de un lenguaje formal.

(b) descripción formal de la gramática de un lenguaje natural.

Cuando nos referimos a lenguaje natural estas reglas combinatorias reciben el nombre de sintaxis, y son inconscientes.

Hay distintos tipos de gramáticas formales que generan lenguajes formales (véase la Jerarquía de

Chomsky).

Imaginemos una gramática con estas dos reglas:

1. A → bAc

2. A → de

Jerarquía de Chomsky

En 1956, Noam Chomsky clasificó las gramáticas en cuatro tipos de lenguajes y esta clasificación es conocida como la jerarquía de Chomsky, en la cual cada lenguaje es descrito por el tipo de gramática generado. Estos lenguajes sirven como base para la clasificación de lenguajes de programación. Los cuatro tipos son: lenguajes recursivamente enumerables, lenguajes sensibles al contexto, lenguajes libres de contexto y lenguajes regulares. Dichos lenguajes también se identifican como lenguajes de tipo 0, 1, 2 y 3.

Existe una exacta correspondencia entre cada uno de estos tipos de lenguajes y particulares arquitecturas de máquinas en el sentido que por cada lenguaje de tipo T hay una arquitectura de máquina A que reconoce el lenguaje de tipo T y por cada arquitectura A hay un tipo T tal que todos los lenguajes reconocidos por A son de tipo T. La correspondencia entre lenguajes y arquitectura son mostrados en la siguiente tabla.

Gramática Lenguaje Autómata Normas de producción

Tipo-0 recursivamente enumerable (LRE) Máquina de Turing (MT) Sin restricciones

Tipo-1 dependiente del contexto (LSC) Autómatas Linealmente Acotados αAβ → αγβ

Tipo-2 independiente del contexto (LLC) Autómata a Pila A → γ

Tipo-3 regular (RL) Autómata Finito A → aBA → a

Lenguajes Recursivamente Enumerables (de tipo 0)

Son los lenguajes naturales. Las gramáticas pueden tener reglas compresoras.

Lenguajes Dependientes del Contexto (sensibles al contexto, de tipo 1)

No existen reglas compresoras, salvo, opcionalmente, la que deriva el axioma a la palabra vacía.

Existen reglas en las que un símbolo no terminal puede derivar a formas senténciales distintas, según los símbolos que aparezcan a su alrededor.

Lenguajes Independientes del Contexto (de contexto libre, de tipo 2)

La mayoría de los lenguajes de programación entran en ésta categoría.

Lenguajes Regulares (de tipo 3)

Se pueden expresar también mediante expresiones regulares.

REPRESENTACIONES DE LENGUAJES Y GRAMÁTICAS ESPECIALES

Notación BNF

Una alternativa que se encuentra con frecuencia es la flotación BNF (forma Backus-Naur). Se sabe que los lados izquierdos de todas las producciones en una gramática de tipo 2 son símbolos no terminales únicos. Para cada uno de tales símbolos w, se combina todas las producciones que tienen a w como lado izquierdo. El símbolo w permanece a la izquierda, y todos los lados derechos asociados con w son enumerados juntos, separados por el símbolo. El símbolo a relacional se reemplazan por el símbolo :: =. Por último, los símbolos no terminales, cuando aparezcan, serán encerrados entre paréntesis agudos ().

Gramáticas regulares y expresiones regulares.

Existe una conexión estrecha entre el lenguaje de una gramática regular y una expresión regular.

Teorema 1. Sea S un conjunto finito y L ∈ S *.

Entonces L es un conjunto regular si y solo si L = L (G) para alguna gramática regular G = (V, S, v0, a ).

El teorema dice que el lenguaje L (G) de una gramática regular G debe ser el conjunto correspondiente a cierta expresión regular sobre S, pero no dice cómo determinar tal expresión regular.

Si la relación de G se especifica en forma BNF o en forma de diagrama de sintaxis.

Autómata

Un autómata es una máquina auto-operada y en ocasiones la palabra es utilizada para describir a un robot.

En informática, (Teoría de los lenguajes formales) se describen tres tipos de autómatas que reconocen tipos diferentes de lenguajes: autómatas finitos, autómatas a pila y máquinas de Turing.

Los

...