Modelos expresados en lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.
Informalmente, el término lenguaje formal se utiliza en muchos contextos (en las ciencias, en derecho, etc.) para referirse a un modo de expresión más cuidadoso y preciso que el habla cotidiana. Hasta finales de la década de 1990, el consenso general era que un lenguaje formal, en el sentido que trata este artículo, era en cierto modo la versión «límite» de este uso antes mencionado: un lenguaje tan formalizado que podía ser usado en forma escrita para describir métodos computacionales. Sin embargo, hoy en día, el punto de vista de que la naturaleza esencial de los lenguajes naturales (sin importar su grado de «formalidad» en el sentido informal antes descrito) difiere de manera importante de aquella de los verdaderos lenguajes formales (en el sentido estricto de este artículo) gana cada vez más adeptos.
Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos a que b, por ejemplo.
La palabra vacía (esto es, la cadena de longitud cero) es permitida y frecuentemente denotada mediante ε o λ. Mientras que el alfabeto es un conjunto finito y cada palabra tiene una longitud también finita, un lenguaje puede bien incluir un número infinito de palabras.
Algunos ejemplos varios de lenguajes formales:
• el conjunto de todas las palabras sobre {a, b}
• el conjunto {a n: n es un número primo}
• el conjunto de todos los programas sintácticamente válidos en un determinado lenguaje de programación
• el conjunto de entradas para las cuales una particular máquina de Turing se detiene.
Los lenguajes formales pueden ser especificados en una amplia variedad de maneras, como:
• cadenas producidas por una gramática formal (ver Jerarquía de Chomsky)
• cadenas producidas por una expresión regular
• cadenas aceptadas por un autómata, tal como una máquina de Turing.
Varias operaciones pueden ser utilizadas para producir nuevos lenguajes a partir de otros dados.
