LENGUAJE FORMAL

žEs un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.

El termino Lenguaje Formal se utiliza en muchos contextos (en ciencia, en derecho, etc.) para referirse a un  modo de expresión mas cuidadoso y preciso que el habla cotidiana.

EJEMPLOS:

Un conjunto de todas las palabras sobre 

{a,b}

El conjunto {an : 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 todas las fórmulas bien formadas en la lógica de primer orden.

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

(Si el lenguaje es regular )

cadenas producidas por una gramatica formal

cadenas descritas por una expresion regular

cadenas aceptadas por un automata

VARIEDADES CONCERNIENTES A LOS LENGUAJES FORMALES 

TEOREMA 1 

El conjunto de lenguajes en general es incontable. 

Afirmar que un alfabeto es no-vacío equivale a que ese alfabeto contenga al menos un símbolo, ergo, basta demostrar que el conjunto de lenguajes en el alfabeto  es incontable. Como sabemos, un lenguaje L en  es un subconjunto de , esto nos lleva a la conclusión de que, el conjunto de todos los lenguajes en  es justamente   y es evidente que  es infinito. 

DEMOSTRACIÓN:

 

Puede derivarse fácilmente que la aseveración delineada en el Teorema 1 es verdadera, porque el conjunto de lenguajes en general es justamente una unión infinita de conjuntos del tipo , donde  es un conjunto infinito contable. 

TEOREMA 2 

Los lenguajes son conjuntos contables. 

Se sabe que un lenguaje  en un alfabeto  es un subconjunto de  y como ya se hizo mención,  es infinito contable, por ende,  es como mucho un conjunto infinito contable (del mismo tamaño que ), la prueba ha culminado. 

TEOREMA 3 

El conjunto de lenguajes formales es contable. 

Como sabemos un lenguaje formal puede ser generado por una gramática formal (o de estructura de frase), lo cual implica que todo lenguaje formal puede ser aceptado por una MT, lo que a su vez implica que se puede definir una biyección entre el conjunto de lenguajes formales y el conjunto de las MT´s 

DEMOSTRACIÓN

: se utiliza el concepto de codificación de MT´s que se introduce en el estudio de las MT´s universales, generalmente se codifica una MT con una función que tiene precisamente como dominio al conjunto de las MT´s  y como codominio , esa función puede ser una biyección si el codominio pasa a ser Y y como  es contable, ese subconjunto también será contable y como existe dicha biyección (entre  e ), la aserción ha sido demostrada, prueba concluida.