Lenguaje formal

En lógica , matemáticas , informática y lingüística , un lenguaje formal es un conjunto de cadenas cuyos símbolos se toman de un conjunto llamado " alfabeto ".

El alfabeto de un lenguaje formal consta de símbolos que se concatenan en cadenas (también llamadas "palabras"). ^{[ 1 ]} Las palabras que pertenecen a un lenguaje formal particular a veces se denominan palabras bien formadas . Un lenguaje formal se define a menudo mediante una gramática formal, como una gramática regular o una gramática libre de contexto .

En informática, los lenguajes formales se utilizan, entre otras cosas, como base para definir las gramáticas de los lenguajes de programación y los lenguajes naturales controlados (es decir, versiones formalizadas de subconjuntos de lenguajes naturales). En la teoría de la complejidad computacional , los problemas de decisión se definen típicamente como lenguajes formales, y las clases de complejidad se definen como los conjuntos de lenguajes formales que pueden ser analizados por máquinas con capacidad computacional limitada. En lógica y fundamentos de las matemáticas , los lenguajes formales se utilizan para representar la sintaxis de los sistemas axiomáticos , y el formalismo matemático es la filosofía que sostiene que todas las matemáticas pueden reducirse a la manipulación sintáctica de lenguajes formales de esta manera.

El campo de la teoría del lenguaje formal estudia principalmente los aspectos puramente sintácticos de dichas lenguas, es decir, sus patrones estructurales internos. La teoría del lenguaje formal surgió de la lingüística como una forma de comprender las regularidades sintácticas de las lenguas naturales . ^{[ 2 ]}

En el siglo XVII, Gottfried Leibniz imaginó y describió la characteristica universalis , un lenguaje universal y formal que utilizaba pictogramas . Posteriormente, Carl Friedrich Gauss investigó el problema de los códigos de Gauss . ^{[ 3 ]}

A mediados del siglo XIX, George Boole estableció el campo del álgebra booleana , que es una forma formal de describir operaciones lógicas utilizando valores de verdad y operadores de conjuntos. En su obra Una investigación de las leyes del pensamiento , demostró que el razonamiento lógico puede expresarse y manipularse mediante ecuaciones simbólicas. ^{[ 4 ]}

Gottlob Frege intentó plasmar las ideas de Leibniz mediante un sistema de notación, esbozado por primera vez en Begriffsschrift (1879) y desarrollado con mayor profundidad en sus dos volúmenes de Grundgesetze der Arithmetik (1893/1903). ^{[ 5 ]} Este sistema describía un «lenguaje formal del lenguaje puro». ^{[ 6 ]}

En la primera mitad del siglo XX, se produjeron varios avances relevantes para los lenguajes formales. Axel Thue publicó cuatro artículos relacionados con las palabras y el lenguaje entre 1906 y 1914. El último de ellos introdujo lo que Emil Post denominó más tarde «Sistemas de Thue» y ofreció un ejemplo temprano de un problema indecidible . ^{[ 7 ]} Posteriormente, Post utilizó este artículo como base para una demostración de 1947 que demostraba que «el problema de las palabras para semigrupos era recursivamente insoluble», ^{[ 8 ]} y más tarde ideó el sistema canónico para la creación de lenguajes formales.

En 1907, Leonardo Torres Quevedo introdujo en Viena un lenguaje formal para la descripción de dibujos mecánicos (dispositivos mecánicos) . Publicó «Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas» («Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas»). ^{[ 9 ]} Heinz Zemanek lo consideró equivalente a un lenguaje de programación para el control numérico de máquinas herramienta. ^{[ 10 ]}

Noam Chomsky ideó una representación abstracta de los lenguajes formales y naturales, conocida como la jerarquía de Chomsky . ^{[ 11 ]} En 1959, John Backus desarrolló la forma Backus-Naur para describir la sintaxis de un lenguaje de programación de alto nivel, siguiendo su trabajo en la creación de FORTRAN . ^{[ 12 ]} Peter Naur fue el secretario/editor del Informe ALGOL60 en el que utilizó la forma Backus-Naur para describir la parte formal de ALGOL60.

En el contexto de los lenguajes formales, un alfabeto puede ser cualquier conjunto ; sus elementos se denominan letras . Un alfabeto puede contener un número infinito de elementos; ^{[ nota 1 ]} sin embargo, la mayoría de las definiciones en la teoría de lenguajes formales especifican alfabetos con un número finito de elementos, y muchos resultados se aplican solo a ellos. A menudo, resulta útil utilizar el término «alfabeto» en su sentido habitual, o, de forma más general, cualquier codificación de caracteres finita como ASCII o Unicode .

Una palabra sobre un alfabeto puede ser cualquier secuencia finita (es decir, cadena ) de letras. El conjunto de todas las palabras sobre un alfabeto Σ se suele denotar por Σ ^* (usando la estrella de Kleene ). La longitud de una palabra es el número de letras que la componen. Para cualquier alfabeto, solo existe una palabra de longitud 0, la palabra vacía , que a menudo se denota por e, ε, λ o incluso Λ. Mediante concatenación se pueden combinar dos palabras para formar una nueva palabra, cuya longitud es la suma de las longitudes de las palabras originales. El resultado de concatenar una palabra con la palabra vacía es la palabra original.

En algunas aplicaciones, especialmente en lógica , el alfabeto también se conoce como vocabulario y las palabras como fórmulas u oraciones ; esto rompe la metáfora letra/palabra y la reemplaza por una metáfora palabra/oración.

Dado un conjunto no vacío${\displaystyle \Sigma }$, un lenguaje formal${\displaystyle L}$encima${\displaystyle \Sigma }$es un subconjunto de${\displaystyle \Sigma ^{*}}$, dónde${\displaystyle \Sigma ^{*}}$es el conjunto de todas las posibles palabras de longitud finita sobre${\displaystyle \Sigma }$Llamamos al conjunto${\displaystyle \Sigma }$el alfabeto de${\displaystyle L}$Por otro lado, dado un lenguaje formal${\displaystyle L}$encima${\displaystyle \Sigma }$, una palabra${\displaystyle w\in \Sigma ^{*}}$está bien formado si${\displaystyle w\in L}$. De manera similar, una expresión${\displaystyle E\subseteq \Sigma ^{*}}$está bien formado si${\displaystyle E\subseteq L}$A veces, un lenguaje formal${\displaystyle L}$encima${\displaystyle \Sigma }$tiene un conjunto de reglas y restricciones claras para la creación de todas las palabras bien formadas posibles a partir de${\displaystyle \Sigma ^{*}}$.

En informática y matemáticas, que no suelen tratar con lenguajes naturales , el adjetivo "formal" a menudo se omite por ser redundante. Por otro lado, podemos decir simplemente "un lenguaje formal".${\displaystyle L}$" cuando su alfabeto${\displaystyle \Sigma }$Queda claro en el contexto.

Si bien la teoría del lenguaje formal suele ocuparse de lenguajes formales descritos por reglas sintácticas, la definición real del concepto de "lenguaje formal" es simplemente la que se ha descrito: un conjunto (posiblemente infinito) de cadenas de longitud finita compuestas a partir de un alfabeto dado, ni más ni menos. En la práctica, existen muchos lenguajes que pueden describirse mediante reglas, como los lenguajes regulares o los lenguajes libres de contexto . La noción de gramática formal se asemeja más al concepto intuitivo de "lenguaje", descrito por reglas sintácticas. Por un uso indebido de la definición, a menudo se piensa que un lenguaje formal particular viene acompañado de una gramática formal que lo describe.

Las siguientes reglas describen un lenguaje formal L sobre el alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:   

• Toda cadena no vacía que no contenga "+" o "=" y que no comience con "0" está en L. 
• La cadena "0" está en L. 
• Una cadena que contiene " =" está en L si y solo si hay exactamente un "=", y separa dos cadenas válidas de L.  
• Una cadena que contiene "+ " pero no "=" está en L si y solo si cada "+" en la cadena separa dos cadenas válidas de L.  
• Ninguna cadena pertenece a L aparte de las implícitas en las reglas anteriores. 

Según estas reglas, la cadena "23+4=555" pertenece a L , pero la cadena "=234=+" no. Este lenguaje formal expresa números naturales , sumas bien formadas e igualdades de suma bien formadas, pero solo expresa su apariencia (su sintaxis ), no su significado ( semántica ). Por ejemplo, en ninguna parte de estas reglas se indica que "0" signifique el número cero, "+" signifique suma, "23+4=555" sea falso, etc. 

Los lenguajes formales se utilizan como herramientas en múltiples disciplinas. Sin embargo, la teoría del lenguaje formal rara vez se ocupa de lenguajes particulares (excepto como ejemplos), sino que se centra principalmente en el estudio de diversos tipos de formalismos para describir lenguajes. Por ejemplo, un lenguaje puede darse como

• aquellas cadenas generadas por alguna gramática formal ;
• aquellas cadenas descritas o coincidentes con una expresión regular particular ;
• aquellas cadenas aceptadas por algún autómata , como una máquina de Turing o un autómata de estados finitos ;
• aquellas cadenas para las cuales algún procedimiento de decisión (un algoritmo que hace una secuencia de preguntas relacionadas de SÍ/NO) produce la respuesta SÍ.

Las preguntas típicas que se suelen plantear sobre este tipo de formalismos incluyen:

• ¿Cuál es su poder expresivo? (¿Puede el formalismo X describir todos los lenguajes que puede describir el formalismo Y ? ¿Puede describir otros lenguajes?)
• ¿Cuál es su grado de reconocibilidad? (¿Qué tan difícil es decidir si una palabra dada pertenece a un idioma descrito por el formalismo X ?)
• ¿Cuál es su comparabilidad? (¿Qué tan difícil es decidir si dos lenguajes, uno descrito en el formalismo X y otro en el formalismo Y , o nuevamente en X , son realmente el mismo lenguaje?).

Sorprendentemente, a menudo la respuesta a estos problemas de decisión es "no se puede hacer en absoluto" o "es extremadamente caro" (con una caracterización de su coste). Por lo tanto, la teoría del lenguaje formal constituye un área de aplicación fundamental de la teoría de la computabilidad y la teoría de la complejidad . Los lenguajes formales pueden clasificarse en la jerarquía de Chomsky en función del poder expresivo de su gramática generativa, así como de la complejidad de su autómata de reconocimiento . Las gramáticas libres de contexto y las gramáticas regulares ofrecen un buen equilibrio entre expresividad y facilidad de análisis sintáctico , y se utilizan ampliamente en aplicaciones prácticas.

Ciertas operaciones con lenguajes son comunes. Esto incluye las operaciones estándar de conjuntos, como la unión, la intersección y el complemento. Otro tipo de operación es la aplicación elemento a elemento de las operaciones con cadenas de caracteres.

Ejemplos: supongamos${\displaystyle L_{1}}$y${\displaystyle L_{2}}$son lenguas sobre algún alfabeto común${\displaystyle \Sigma }$.

• La concatenación${\displaystyle L_{1}\cdot L_{2}}$consta de todas las cadenas de la forma${\displaystyle vw}$dónde${\displaystyle v}$es una cadena de${\displaystyle L_{1}}$y${\displaystyle w}$es una cadena de${\displaystyle L_{2}}$.
• La intersección${\displaystyle L_{1}\cap L_{2}}$de${\displaystyle L_{1}}$y${\displaystyle L_{2}}$consta de todas las cadenas que están contenidas en ambos idiomas.
• El complemento${\displaystyle \neg L_{1}}$de${\displaystyle L_{1}}$con respecto a${\displaystyle \Sigma }$consta de todas las cadenas más${\displaystyle \Sigma }$que no están en${\displaystyle L_{1}}$.
• La estrella de Kleene : el lenguaje que consiste en todas las palabras que son concatenaciones de cero o más palabras en el idioma original;
• Reversión :
  • Sea ε la palabra vacía, entonces${\displaystyle \varepsilon ^{R}=\varepsilon }$, y
  • para cada palabra no vacía${\displaystyle w=\sigma _{1}\cdots \sigma _{n}}$(dónde${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$son elementos de algún alfabeto), sea${\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}$,
  • luego para un lenguaje formal${\displaystyle L}$,${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$.
• homomorfismo de cadenas

Estas operaciones con cadenas se utilizan para investigar las propiedades de cierre de las clases de lenguajes. Una clase de lenguajes es cerrada bajo una operación particular cuando dicha operación, aplicada a los lenguajes de la clase, siempre produce un lenguaje de la misma clase. Por ejemplo, se sabe que los lenguajes libres de contexto son cerrados bajo la unión, la concatenación y la intersección con lenguajes regulares , pero no bajo la intersección ni el complemento. La teoría de tríos y familias abstractas de lenguajes estudia las propiedades de cierre más comunes de las familias de lenguajes por derecho propio. ^{[ 14 ]}

• Combinatoria de palabras
• Método formal
• monoide libre
• Marco gramatical
• Lista de sistemas formales
• Notación matemática
• Cadenas de caracteres (informática)

• "Lenguaje formal" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Universidad de Maryland , Definiciones de lenguaje formal. Archivado el 16 de febrero de 2008 en Wayback Machine.
• James Power, "Notas sobre teoría del lenguaje formal y análisis sintáctico". Archivado el 21 de noviembre de 2007 en Wayback Machine , 29 de noviembre de 2002.
• Borradores de algunos capítulos del "Manual de teoría del lenguaje formal", vol. 1–3, G. Rozenberg y A. Salomaa (eds.), Springer Verlag , (1997):
  • Alexandru Mateescu y Arto Salomaa, "Prefacio" en el volumen 1, págs. v-viii, y "Lenguajes formales: una introducción y una sinopsis", capítulo 1 en el vol. 1, págs. 1–39
  • Sheng Yu, "Lenguajes regulares", Capítulo 2 en Vol. 1
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Lenguajes libres de contexto y autómatas de pila", Capítulo 3 en Vol. 1
  • Christian Choffrut y Juhani Karhumäki, "Combinatoria de palabras", capítulo 6 en vol. 1
  • Tero Harju y Juhani Karhumäki, "Morfismos", Capítulo 7 en el vol. 1, págs. 439–510
  • Jean-Eric Pin, "Semigrupos sintácticos", Capítulo 10 en Vol. 1, págs. 679–746
  • M. Crochemore y C. Hancart, "Autómatas para la coincidencia de patrones", Capítulo 9 en Vol. 2
  • Dora Giammarresi, Antonio Restivo, "Lenguajes bidimensionales", Capítulo 4 en vol. 3, págs. 215–267