En lógica , matemáticas , informática y lingüística , un lenguaje formal consta de palabras cuyas letras se toman de un alfabeto y están bien formadas según un conjunto específico de reglas llamado gramática formal .
El alfabeto de un lenguaje formal consta de símbolos, letras o fichas que se concatenan en cadenas llamadas palabras. [1] Las palabras que pertenecen a un lenguaje formal particular a veces se denominan palabras bien formadas o fórmulas bien formadas . Un lenguaje formal a menudo se define mediante una gramática formal como una gramática regular o una gramática libre de contexto , que consta de sus reglas de formación .
En informática, los lenguajes formales se utilizan, entre otros, como base para definir la gramática de los lenguajes de programación y las versiones formalizadas de subconjuntos de lenguajes naturales en los que las palabras del lenguaje representan conceptos asociados con significados o semántica . 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 potencia 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 de que todas las matemáticas pueden reducirse a la manipulación sintáctica de los lenguajes formales de esta manera.
El campo de la teoría del lenguaje formal estudia principalmente los aspectos puramente sintácticos de dichos lenguajes, 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 .
En el siglo XVII, Gottfried Leibniz imaginó y describió la featurea universalis , un lenguaje universal y formal que utilizaba pictografías . Posteriormente, Carl Friedrich Gauss investigó el problema de los códigos de Gauss . [2]
Gottlob Frege intentó hacer realidad las ideas de Leibniz, a través de un sistema de notación esbozado por primera vez en Begriffsschrift (1879) y desarrollado más completamente en sus dos volúmenes Grundgesetze der Arithmetik (1893/1903). [3] Esto describía un "lenguaje formal de lenguaje puro". [4]
En la primera mitad del siglo XX, se realizaron 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 Thue" y dio un ejemplo temprano de un problema indecidible . [5] Post utilizaría más tarde este artículo como base para una prueba de 1947 "de que el problema verbal para semigrupos era recursivamente insoluble", [6] 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". [7] Heinz Zemanek lo calificó como equivalente a un lenguaje de programación para el control numérico de máquinas herramienta. [8]
Noam Chomsky ideó una representación abstracta de los lenguajes formales y naturales, conocida como jerarquía de Chomsky . [9] 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 . [10] Peter Naur fue el secretario/editor del Informe ALGOL60 en el que utilizó la forma Backus-Naur para describir la parte formal de ALGOL60.
Un alfabeto , en el contexto de los lenguajes formales, puede ser cualquier conjunto ; sus elementos se llaman letras . Un alfabeto puede contener una cantidad infinita de elementos; [nota 1] sin embargo, la mayoría de las definiciones en la teoría del lenguaje formal especifican alfabetos con un número finito de elementos, y muchos resultados se aplican solo a ellos. A menudo tiene sentido utilizar un alfabeto en el sentido habitual de la palabra o, más generalmente, cualquier codificación de caracteres finitos como ASCII o Unicode .
Una palabra sobre un alfabeto puede ser cualquier secuencia finita (es decir, una cadena ) de letras. El conjunto de todas las palabras sobre un alfabeto Σ generalmente se denota por Σ * (usando la estrella de Kleene ). La longitud de una palabra es el número de letras que la componen. Para cualquier alfabeto, sólo hay 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 se conocen como fórmulas u oraciones ; esto rompe la metáfora de letra/palabra y la reemplaza por una metáfora de palabra/oración.
Un lenguaje formal L sobre un alfabeto Σ es un subconjunto de Σ * , es decir, un conjunto de palabras sobre ese alfabeto. A veces, los conjuntos de palabras se agrupan en expresiones, mientras que se pueden formular reglas y restricciones para la creación de "expresiones bien formadas".
En informática y matemáticas, que normalmente no se ocupan de lenguajes naturales , el adjetivo "formal" a menudo se omite por ser redundante.
Si bien la teoría del lenguaje formal generalmente se ocupa de los lenguajes formales que se describen mediante algunas reglas sintácticas, la definición real del concepto "lenguaje formal" es solo la anterior: un conjunto (posiblemente infinito) de cadenas de longitud finita compuestas a partir de un alfabeto determinado, Nada mas y nada 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 puede estar más cerca del concepto intuitivo de "lenguaje", descrito por reglas sintácticas. Por un abuso de la definición, a menudo se piensa que un lenguaje formal particular está equipado con 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, +, =}:
Según estas reglas, la cadena "23+4=555" está en L , pero la cadena "=234=+" no. Este lenguaje formal expresa números naturales , sumas bien formadas e igualdades de sumas bien formadas, pero expresa sólo su apariencia (su sintaxis ), no lo que significan ( semántica ). Por ejemplo, en ninguna parte de estas reglas hay ninguna indicación de que "0" significa el número cero, "+" significa suma, "23+4=555" es falso, etc.
Para lenguajes finitos, se pueden enumerar explícitamente todas las palabras bien formadas. Por ejemplo, podemos describir un lenguaje L simplemente como L = {a, b, ab, cba}. El caso degenerado de esta construcción es el lenguaje vacío , que no contiene ninguna palabra ( L = ∅ ).
Sin embargo, incluso en un alfabeto finito (no vacío) como Σ = {a, b} hay un número infinito de palabras de longitud finita que potencialmente pueden expresarse: "a", "abb", "ababba", " aaababbbbaab", .... Por lo tanto, los lenguajes formales suelen ser infinitos, y describir un lenguaje formal infinito no es tan simple como escribir L = {a, b, ab, cba}. A continuación se muestran algunos ejemplos de lenguajes formales:
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 ocupa principalmente del estudio de varios tipos de formalismos para describir lenguajes. Por ejemplo, un idioma se puede dar como
Las preguntas típicas que se hacen sobre tales formalismos incluyen:
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 qué tan caro). Por lo tanto, la teoría del lenguaje formal es un área de aplicación importante 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 según el poder expresivo de su gramática generativa, así como la complejidad de su reconocimiento autómata . Las gramáticas libres de contexto y las gramáticas regulares proporcionan un buen equilibrio entre expresividad y facilidad de análisis y se utilizan ampliamente en aplicaciones prácticas.
Ciertas operaciones en idiomas son comunes. Esto incluye las operaciones de conjuntos estándar, como unión, intersección y complemento. Otra clase de operación es la aplicación de operaciones de cadena por elementos.
Ejemplos: suponer y son lenguas sobre algún alfabeto común .
Estas operaciones de cadenas se utilizan para investigar las propiedades de cierre de clases de idiomas. Una clase de idiomas se cierra bajo una operación particular cuando la operación, aplicada a los idiomas de la clase, siempre produce nuevamente un idioma en la misma clase. Por ejemplo, se sabe que los lenguajes libres de contexto están cerrados en unión, concatenación e intersección con lenguajes regulares , pero no cerrados en intersección o complemento. La teoría de tríos y familias abstractas de lenguas estudia las propiedades de cierre más comunes de las familias de lenguas por derecho propio. [11]
Un compilador suele tener dos componentes distintos. Un analizador léxico , a veces generado por una herramienta como lex, identifica los tokens de la gramática del lenguaje de programación, por ejemplo, identificadores o palabras clave , literales numéricos y de cadena, signos de puntuación y operadores, que a su vez se especifican mediante un lenguaje formal más simple, generalmente mediante comandos regulares. expresiones . En el nivel conceptual más básico, un analizador , a veces generado por un generador de analizadores como yacc, intenta decidir si el programa fuente es sintácticamente válido, es decir, si está bien formado con respecto a la gramática del lenguaje de programación para el cual se creó el compilador.
Por supuesto, los compiladores hacen más que simplemente analizar el código fuente: normalmente lo traducen a algún formato ejecutable. Debido a esto, un analizador generalmente genera más que una respuesta de sí/no, generalmente un árbol de sintaxis abstracta . Esto se utiliza en etapas posteriores del compilador para generar eventualmente un ejecutable que contenga código de máquina que se ejecute directamente en el hardware, o algún código intermedio que requiera una máquina virtual para ejecutarse.
En lógica matemática , una teoría formal es un conjunto de oraciones expresadas en un lenguaje formal.
Un sistema formal (también llamado cálculo lógico , o sistema lógico ) consta de un lenguaje formal junto con un aparato deductivo (también llamado sistema deductivo ). El aparato deductivo puede consistir en un conjunto de reglas de transformación , que pueden interpretarse como reglas de inferencia válidas, o en un conjunto de axiomas , o tener ambos. Se utiliza un sistema formal para derivar una expresión a partir de una o más expresiones. Aunque un lenguaje formal puede identificarse con sus fórmulas, un sistema formal no puede identificarse igualmente con sus teoremas. Dos sistemas formales pueden tener los mismos teoremas y, sin embargo, diferir de alguna manera significativa en la teoría de la prueba (una fórmula A puede ser una consecuencia sintáctica de una fórmula B en uno pero no en otro, por ejemplo).
Una prueba o derivación formal es una secuencia finita de fórmulas bien formadas (que pueden interpretarse como oraciones o proposiciones ), cada una de las cuales es un axioma o se sigue de las fórmulas anteriores en la secuencia mediante una regla de inferencia . La última oración de la secuencia es un teorema de un sistema formal. Las demostraciones formales son útiles porque sus teoremas pueden interpretarse como proposiciones verdaderas.
Los lenguajes formales son enteramente de naturaleza sintáctica, pero se les puede dar una semántica que dé significado a los elementos del lenguaje. Por ejemplo, en lógica matemática , el conjunto de posibles fórmulas de una lógica particular es un lenguaje formal, y una interpretación asigna un significado a cada una de las fórmulas (normalmente, un valor de verdad ).
El estudio de las interpretaciones de los lenguajes formales se denomina semántica formal . En lógica matemática, esto a menudo se hace en términos de teoría de modelos . En la teoría de modelos, los términos que aparecen en una fórmula se interpretan como objetos dentro de estructuras matemáticas , y reglas fijas de interpretación de composición determinan cómo se puede derivar el valor de verdad de la fórmula a partir de la interpretación de sus términos; un modelo para una fórmula es una interpretación de términos tal que la fórmula se vuelve verdadera.
Un alfabeto es un conjunto finito.
