licenciad

3.2 AUTÓMATAS FINITOS. LENGUAJES RECONOCIDOS POR AUTÓMATAS FINITOS. DISTINGUIBILIDAD

3.2.1 MEMORIA NECESARIA PARA RECONOCER UN LENGUAJE

3.2.2 TRANSICIONES ENTRE ESTADOS

3.2.3 FUNCIÓN DE TRANSICIÓN EXTENDIDA

3.2.4 CARACTERIZACIÓN DE LOS LENGUAJES REGULARES

3.2.5 DISTINGUIBILIDAD ENTRE PALABRAS

3.2.5.1 Teorema de la distinguibilidad
3.2.5.2 Aplicaciones:Diseño de AFs. Lenguajes no regulares

3.2 AUTÓMATAS FINITOS
La segunda caracterización de los lenguajes regulares es que son reconocidos por autómatas finitos. En este enfoque de la teoría de la Informática, hemos comenzado por los lenguajes más simples(los regulares) y, a continuación, vamos a ver los requisitos mínimos de un modelo abstracto de máquina(autómata finito) para procesarlas palabras de *, de forma que sepa distinguir si la palabra es del lenguaje que el autómata reconoce o no.
3.2.1 MEMORIA NECESARIA PARA RECONOCER UN LENGUAJE
Reconocer un L es: Dada cualquier x  *, responder SÍ si x  L y NO si x  L.
Los LR pueden ser caracterizados, como todos los LFs, en términos de la "memoria" requerida para reconocerlos.
La forma de procesar lainformación por el autómata
A la entrada se pone la palabra que se somete a ser leída por el autómata. El procesamiento de la información lo hemos restringido a una pasada única de la palabra de izquierda a derecha. Esta manera de considerar el procesamiento es arbitraria, pero es estándar; eso ayuda a clasificar la información que debe ser recordada de la parte de la cadena que ya ha sidoprocesada. Ello permite clasificar los Ls sobre la base de la cantidad de memoria, en la forma de número de estados distintos, que se necesita disponer guardando en cada caso la información necesaria para la clasificación de las palabras. Dada una palabra, o bien es del L o bien no.
La forma de procesar es ir tomando decisiones acerca de si la palabra puede pertenecer al lenguaje cada vez que se haleído un carácter o si, por el contrario, se puede decidir, sin llegar al final de la cadena, que ésta no pertenece a L . En este último caso no es necesario llegar al final. En el primer caso, debemos estar siempre en una situación en la que "recordamos" toda la información casuística necesaria contenida en la subcadena leída para poder seguir tomando decisiones tentativas: bien "si hubiese terminadola palabra, ésta pertenecería a L", o bien "si hubiese terminado la palabra, ésta no pertenecería a L".
Cada estado se asocia a un conjunto de palabras de * , de forma que la unión de esos conjuntos sea  * y la intersección sea . En todo momento el autómata permanece en un estado y sólo en uno (esta propiedad no se mantendrá para los autómatas no deterministas). Forzosamente unode los estados ha de ser el estado inicial, o sea el estado en el que se encuentra el autómata mientras no se lee nada, ni siquiera la letra más a la izquierda de la palabra; es decir, cuando se lee . Así pues todo autómata tiene que tener, al menos, un estado (el estado inicial).
3.2.2 ESTADOS y TRANSICIONES
Sea L = *. En este caso no hay que distinguir unas palabras de otras. Larespuesta, después de haber leído la palabra completa, ha de ser SÍ, independientemente de cuál sea la palabra. Por consiguiente no hay nada que recordar. El AF tiene un solo estado y éste es de aceptación, ya que cualquier palabra de entrada es de *.


Explicación: Un AF tiene, al menos, un estado. En este caso es el “estado inicial”; es decir, elestado en el que permanece cuando aún no ha empezado a trabajar, o bien cuando ha leído la palabra ‘‘. Si ésta pertenece al L que reconoce el AF, el estado inicial es de aceptación. Los estados de aceptación se marcan para distinguirlos de los de no aceptación. Por tanto, el AF que reconoce * se representa gráficamente así, habiendo tenido en cuenta sólo los estados, y no las transiciones...