AUTÓMATAS Y LENGUAJES FORMALES

1. AUTÓMATAS Y LENGUAJES FORMALES.

La teoría de autómatas esta estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer. Un autómata es un modelo matemático para una máquina de estado finita, la cual es una máquina que, dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). Esta función de transición dice al autómata a que estado cambiar dados unos determinados estados y símbolos. La entrada es leída símbolo por símbolo, hasta que es "consumida" completamente una vez que la entrada se ha agotado, el autómata se detiene. Dependiendo del estado en el que el autómata para, se dice que este ha aceptado o rechazado la entrada, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

Para el concepto de lenguaje necesitaremos definir los términos siguientes.

- Alfabeto: Es un conjunto finito y no vacío de símbolos.

- Palabra: Es la secuencia finita de símbolos de un determinado alfabeto. También se le conoce como cadena

- Frase: Es el conjunto de cadenas o palabras que tienen sentido, significado y lógica.

- Cadena Vacía: Es una palabra que no tiene símbolo y su longitud es 0.

- Lenguaje: Es un conjunto compuesto por cadenas de longitud finita formadas por símbolos tomados de un mismo alfabeto. Si el lenguaje construido con el alfabeto , y tenemos cualquier subconjunto L de *. Diremos que un lenguaje es finito, si es finito el número de cadenas de que consta; en otro caso diremos que es infinito. El lenguaje vacío no tiene ninguna cadena (que no debe confundirse con el lenguaje que solo tiene la cadena vacía).

Gramáticas formales

Una vez dada esta definición tan general de lenguaje, el problema inicial que se nos presenta es como distinguir con precisión las cadenas que pertenecen a un lenguaje L...

...