Lenguaje formal

En matemáticas, lógica, y ciencias de la computación, un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita en los casos más simples o expresiones válidas (formuladas por palabras) formadas a partir de un alfabeto (conjunto de caracteres) finito. El nombre lenguaje se justifica porque las estructuras que con este se forman tienen reglas de buena formación (gramática) e interpretación semántica (significado) en una forma muy similar a los lenguajes hablados o naturales.

Un posible alfabeto sería, digamos, $\{a,b\}\,$, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, $ababba\,$. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos $a\,$ que $b\,$, por ejemplo.

La palabra vacía (esto es, la cadena de longitud cero) se permite en este tipo de lenguajes, notándose frecuentemente mediante $\epsilon \,$, $e\,$ ó $\lambda \,$. A diferencia de lo que ocurre con el alfabeto (que es un conjunto finito) y con cada palabra (que tiene una longitud también finita), un lenguaje puede estar compuesto por un número infinito de palabras.

Ejemplos de lenguajes formales

• El conjunto de todas las palabras sobre $\{a,b\}\,$.
• El conjunto $\{a^{n}:n\}\,$ es un número primo.
• El conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de programación.
• El conjunto de sentencias bien formadas en lógica de predicados.

Especificación de lenguajes formales

Los lenguajes formales se pueden especificar de una amplia variedad de formas, como por ejemplo:

• Cadenas producidas por una gramática formal (véase Jerarquía de Chomsky).
• Cadenas producidas por una expresión regular.
• Cadenas aceptadas por un autómata, tal como una máquina de Turing.

Operaciones

Se pueden utilizar varias operaciones para producir nuevos lenguajes a partir de otros dados. Supóngase que L₁ y L₂ son lenguajes sobre un alfabeto común. Entonces:

• la concatenación L₁L₂ consiste de todas aquellas palabras de la forma vw donde v es una palabra de L₁ y w es una palabra de L₂
• la intersección L₁&L₂ consiste en todas aquellas palabras que están contenidas tanto en L₁ como en L₂
• la unión L₁|L₂ consiste en todas aquellas palabras que están contenidas ya sea en L₁ o en L₂
• el complemento ~L₁ consiste en todas aquellas palabras producibles sobre el alfabeto de L₁ que no están ya contenidas en L₁
• el cociente L₁/L₂ consiste de todas aquellas palabras v para las cuales existe una palabra w en L₂ tales que vw se encuentra en L₁
• la estrella L₁^{* consiste de todas aquellas palabras que pueden ser escritas de la forma W₁W₂...W_n donde todo W_i se encuentra en L₁ y n ≥ 0. (Nótese que esta definición incluye a ε en cualquier L*)}
• la intercalación L₁*L₂ consiste de todas aquellas palabras que pueden ser escritas de la forma v₁w₁v₂w₂...v_nw_n; son palabras tales que la concatenación v₁...v_n está en L₁, y la concatenación w₁...w_n está en L₂

Una pregunta que se hace típicamente sobre un determinado lenguaje formal L es cuán difícil es decidir si incluye o no una determinada palabra v. Este tema es del dominio de la teoría de la computabilidad y la teoría de la complejidad computacional.

Por contraposición al lenguaje propio de los seres vivos y en especial el lenguaje humano, considerados lenguajes naturales, se denomina lenguaje formal a los lenguajes «artificiales» propios de las matemáticas o la informática, los lenguajes artificiales son llamados lenguajes formales (incluyendo lenguajes de programación). Sin embargo, el lenguaje humano tiene una característica que no se encuentra en los lenguajes de programación: la diversidad.

En 1956, Noam Chomsky creó la Jerarquía de Chomsky para organizar los distintos tipos de lenguaje formal.

Verdades concernientes a los lenguajes formales

Teorema 1: El conjunto de lenguajes en general (incluyendo los no-formales) es incontable.

Lema 1: El conjunto de lenguajes en un alfabeto no vacío dado es incontable

Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto $\{a\}\,$ es incontable. Como sabemos, un lenguaje L en $\{a\}\,$ es un subconjunto de $\{a\}^{*}\,$, esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en $\{a\}\,$ es justamente $2^{\{}a\}^{*}\,$ (el conjunto de todos los subconjuntos o conjunto potencia de $\{a\}^{*}\,$) y es evidente que $\{a\}^{*}\,$ es infinito (de hecho; contable), también ha sido demostrado que si $A$ es un conjunto infinito (contable o incontable), entonces $2^{A}$ es mayor que $A$ porque $2^{A}$ pasa a ser un conjunto infinito de órdenes del infinito, al ser mayor, no existirá biyección entre $A$ y $2^{A}$, lo que hace a $2^{A}$ un conjunto infinito incontable, la prueba ha finalizado.

Demostración del Teorema 1: Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo $2^{A}$, donde $A$ es un conjunto infinito contable.

Teorema 2: Los lenguajes son conjuntos contables

Se sabe que un lenguaje $L$ en un alfabeto $\Sigma$ es un subconjunto de $\Sigma ^{*}$ y como ya se hizo mención, $\Sigma ^{*}$ es infinito incontable, por ende, $L$ es como mucho un conjunto infinito incontable (del mismo tamaño que $\Sigma ^{*}$), la prueba ha culminado.

Teorema 3: El conjunto de lenguajes formales es contable

Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s (debido a la propiedad transitiva de la relación "existe biyección entre $A$ y $B$"). Para demostrar el teorema se utilizará el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s (lo llamaremos $X$) y como codominio $\{0,1\}^{*}\,$, esa función puede ser una biyección si el codominio pasa a ser Y (un subconjunto de $\{0,1\}^{*}\,$) y como $\{0,1\}^{*}\,$ es contable, ese subconjunto también será contable y como existe dicha biyección (entre $X$ e $Y$), la aserción ha sido demostrada, prueba concluida.

Véase también

• Teoría de la computación
• Ciencias de la computación
• Lenguaje de especificación
• Lenguaje formalizado

Enlace externo

• Libro electrónico gratuito sobre autómatas y lenguajes formales (Tecnológico de Monterrey, México)