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 , o .
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 L1 y L2 son lenguajes sobre un alfabeto común. Entonces:
