SSL: introducción al diseno de autómatas finitos 1

** Cada AF reconoce un ÚNICO LR. En cambio, para un LR pueden existir muchos AFs que lo reconozcan, como veremos más adelante.

5.2  AFs QUE RECONOCEN LRs FINITOS

Los LRs finitos se representan mediante ERs que utilizan tres operadores: concatenación, unión y potencia, aunque éste último solo es un “simplificador”, y se reduce a la aplicación reiterada del operador concatenación.

En el ejemplo anterior hemos visto cómo se representa una concatenación en el DTs de un AF: es, simplemente, una transición concatenada con otra transición (analice el diagrama dibujado y verifique que la concatenación de los caracteres a y b que forman la palabra ab se “transforma” en dos transiciones consecutivas, la primera etiquetada con el carácter a y la segunda etiquetada con el carácter b).

El DT para el operador “unión” es un poco más complicado porque requiere que, desde un estado, partan dos transiciones a, normalmente, diferentes estados.

Ejemplo 2

Sea la ER ab + aab, la cual representa un LR con dos palabras. Dado que ambas palabras comienzan con el carácter a, esta expresión también puede escribirse así: a (b + ab).

El DT del AF que reconoce a este LR es:

La primera a, que es común a ambas palabras, “mueve” al AF del estado inicial al estado intermedio 1. Aquí aparece la bifurcación que implementa al operador unión: un camino conduce al estado final 2, para reconocer a la palabra ab, y el otro camino conduce al estado 3 y luego al estado final 4, para reconocer a la palabra aab.

** Todo AF es construido sobre un alfabeto determinado, el cual coincide con el del LR que reconoce. La cadena que el AF debe procesar sólo puede contener caracteres de este alfabeto. Los caracteres que etiquetan las transiciones en el DT de un AF son los que constituyen el alfabeto en cuestión.

Ejemplo 3

Sea la ER a + ab + aab. Esta ER se ha formado agregándole la palabra a a la ER del ejemplo anterior.

Dada la similitud que existe entre ambas ERs, es de suponer que también serán similares los DTs de los AFs que reconocen a los LRs representados. Efectivamente, así es. El nuevo AF, sobre el alfabeto {a, b}, tiene el siguiente Diagrama de Transiciones:

La única e importante diferencia que existe entre este AF y el del ejemplo anterior es que, ahora, el estado 1 debe ser un estado final para que se pueda reconocer a la palabra a. Observe que la denominación estado final no significa “último estado del AF, necesariamente”, sino estado de aceptación, estado de reconocimiento, como ocurre, en este caso, con el estado 1.

No es obligatorio que un AF tenga un estado final para cada palabra del LR reconocido, como se ve en el siguiente caso:

Ejemplo 4

Se construye el siguiente AF sobre el alfabeto {0, 1} que reconoce un LR que tiene dos palabras. El AF tiene un solo estado final:

*** ¿Qué LR reconoce este AF?

Como conclusión de esta sección sobre Autómatas Finitos que reconocen Lenguajes Regulares finitos, observe que una palabra de longitud 1 es reconocida por un autómata con una transición y dos estados, una palabra de longitud 2 es aceptada por un autómata con dos transiciones y tres estados, etc.