Lenguaje formal
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 de acuerdo con un conjunto específico de reglas.
El alfabeto de un lenguaje formal consta de símbolos, letras o tokens que se concatenan en cadenas del lenguaje. [1] Cada cadena concatenada de símbolos de este alfabeto se denomina palabra, y 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 por medio de una gramática formal , como una gramática regular o una gramática libre de contexto , que consiste en sus reglas de formación .
El campo de la teoría formal del lenguaje 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 los lenguajes naturales . 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 que están asociados con significados o semánticas particulares . En la teoría de la complejidad computacional , los problemas de decisiónse 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 poder computacional limitado. En la lógica y los 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.
Se cree que el primer uso del lenguaje formal fue el Begriffsschrift de 1879 de Gottlob Frege , que significa "escritura de conceptos", que describía un "lenguaje formal, inspirado en el de la aritmética, para el pensamiento puro". [2]
El primer sistema semi-Thue de Axel Thue , que se puede utilizar para reescribir cadenas, influyó en las gramáticas formales .
Un alfabeto , en el contexto de los lenguajes formales, puede ser cualquier conjunto , aunque a menudo tiene sentido usar un alfabeto en el sentido habitual de la palabra, o más generalmente un conjunto de caracteres como ASCII o Unicode . Los elementos de un alfabeto se llaman sus 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 del lenguaje formal especifican alfabetos con un número finito de elementos, y la mayoría de los resultados se aplican solo a ellos.
