Lenguaje formal

En matemáticas, lógica y ciencias de la computación, un lenguaje formal es un lenguaje cuyos símbolos son primitivos y las reglas para unir esos símbolos están formalmente especificadas.^[1]​^[2]​ Al conjunto de los símbolos primitivos se le llama el alfabeto (o vocabulario) del lenguaje, y al conjunto de las reglas se le llama la gramática formal (o sintaxis). A una cadena de símbolos formada de acuerdo a la gramática se le llama una fórmula bien formada (o palabra) del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas.

Por ejemplo, un alfabeto podría ser el conjunto {a,b}, y una gramática podría definir a las fórmulas bien formadas como aquellas que tienen el mismo número de símbolos a que b. Entonces, algunas fórmulas bien formadas del lenguaje serían: ab, ba, abab, ababba, etc., y el lenguaje formal sería el conjunto de todas esas fórmulas bien formadas.

Para algunos lenguajes formales existe una semántica formal que puede interpretar y dar significado a las fórmulas bien formadas del lenguaje. Sin embargo, una semántica formal no es condición necesaria para definir un lenguaje formal, y eso es una diferencia esencial con los lenguajes naturales.

En algunos lenguajes formales, la palabra vacía (esto es, la cadena de símbolos de longitud cero) está permitida, notándose frecuentemente mediante ${displaystyle epsilon ,}$, ${displaystyle e,}$ o ${displaystyle lambda ,}$.

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

(Si el lenguaje es regular)

Las cadenas están formadas por un conjunto de símbolos que pertenecen a un mismo lenguaje, existen dos formas de componer una sentencia o función con los símbolos:

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

Sean los ${displaystyle L_{i}}$ lenguajes, de forma tal que para cada ${displaystyle i}$ entonces ${displaystyle L_{i}}$ esté formado por todas las palabras que pueden surgir de concatenar ${displaystyle i}$ palabras del lenguaje ${displaystyle L}$. Por ejemplo, si ${displaystyle L=left{v,w ight}}$, entonces ${displaystyle L_{3}=left{v.v.v,v.v.w,v.w.v,v.w.w,w.v.v,w.v.w,w.w.v,w.w.w ight}}$ En base al conceptor anterior pueden definirise la clausuras mencionadas anteriormente:

Por lo tanto se deduce que ${displaystyle L^{*}=left{lambda ight}cup 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.

Los lenguajes formales derivados de un alfabeto que consta de una sola letra, conocida como lenguajes unarios, pueden ser considerados como conjuntos de números naturales, y las cuestiones de la representación de tales conjuntos mediante los dispositivos básicos de la teoría de lenguaje formal forman un tema especial de estudio. Los lenguajes unarios formales son básicamente conjuntos periódicos (Jez & Okhotin, 2007).^[3]​

Los lenguajes unarios formales son caracterizados por sistemas de ecuaciones de lenguaje de la forma general:

${displaystyle {egin{cases}X_{1}=varphi _{1}{igl (}X_{1},...,X_{n}{igr )},\.\.\.\X_{n}=varphi _{n}{igl (}X_{1},...,X_{n}{igr )}\end{cases}}}$ (1)

Con operaciones diferentes y permitidas sobre su lado derecho. Los lenguajes libres de contexto o incontextuales se obtienen mediante el uso de la concatenación y unión del sistema. Como lo dice Jez & Okhotin (2007). Si la concatenación se limita a un solo lado lineal (es decir, cada concatenación que aparece en alguna parte derecha es de la forma w · φ por alguna cadena constante w), entonces las soluciones representan exactamente los lenguajes regulares. Por último, respaldando a los autómatas, como lo demuestra Okhotin (2004), se pueden simular mediante ecuaciones con unión, intersección y concatenación lineal de dos caras.

Cuando hablamos de lenguajes debemos considerar la gramática que los rigen. Barash & Okhotin (2014)^[4]​ nos dicen que las gramáticas libres de contexto se entienden mejor como una lógica para definir la sintaxis de los lenguajes. En esta lógica, las definiciones son inductivas, por lo que las propiedades de una cadena están determinadas por las propiedades de sus subseries. Así es como una regla S → aSb afirma que si una cadena a^n-1bⁿ¹ tiene la propiedad S, entonces las cadenas aⁿbⁿ tienen la propiedad S también. Además de la concatenación, el formalismo de esta lógica incluye una operación de disyunción, representada por tener varias reglas para un único símbolo.