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.

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) es permitida y frecuentemente denotada mediante ε o λ. Mientras que el alfabeto es un conjunto finito y cada palabra tiene una longitud también finita, un lenguaje puede bien incluir un número infinito de palabras.

Algunos ejemplos varios de lenguajes formales:

• el conjunto de todas las palabras sobre {a, b}
• el conjunto {aⁿ: 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 entradas para las cuales una particular máquina de Turing se detiene.

Los lenguajes formales pueden ser especificados en una amplia variedad de maneras, como:

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

Varias operaciones pueden ser utilizadas 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.