Lenguaje formal

De Wikipedia, la enciclopedia libre

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 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.

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 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.

[editar] 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.

[editar] 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.

[editar] 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.

[editar] Véase también

[editar] Enlace externo

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