Apunte Te Rico 2

 

♦ RELACIÓN ENTRE AUTÓMATAS FINITOS Y LENGUAJES REGULARES
Comenzaremos el estudio de la íntima relación que existe entre autómatas y lenguajes, a partir del nivel
más simple. Este estudio no sólo producirá una mayor comprensión de estas máquinas y estos lenguajes,
sino que también unificará conceptos vistos anteriormente. Veremos que las siguientes aseveraciones son
equivalentes:
1.- Ellenguaje L es reconocido por algún aceptor de estados finitos.
2.- El lenguaje L es generado por alguna gramática regular.
3.- El lenguaje L es descripto por alguna expresión regular.

✁

1. Aceptores de Estados Finitos
Vimos al comenzar el curso que una relación entre máquinas abstractas y lenguajes se puede establecer
por medio de aceptores, máquinas que clasifican cada string de entrada como aceptadoo rechazado.
Un autómata finito con salida asociada a estado y alfabeto de salida {0, 1} puede ser interpretado como
un aceptor de este tipo. Los estados de esta máquina pueden ser clasificados en dos clases:
1.- Estados de aceptación: Cuya salida es 1.
2.- Estados de rechazo: Cuya salida es 0.
El lenguaje reconocido por un aceptor de estados finitos consiste precisamente de los strings que tomana la máquina desde su estado inicial y la llevan a un estado de aceptación. En lugar de especificar los
estados de aceptación por medio de una función de salida, será más simple identificar el subconjunto de los
estados de la máquina que son estados de aceptación. En un diagrama de estados, los nodos
correspondientes a estados de aceptación se dibujan con dobles circunferencias.

✁

1.1. Aceptoresno Determinísticos
Nuestra primera etapa es relacionar aceptores de estados finitos con gramáticas regulares.
Hemos visto que una gramática consiste de un conjunto de reglas de producción, que pueden ser
aplicadas en cualquier orden consistente, con el propósito de derivar un string terminal. La gramática es
permisiva en el sentido que hay puntos en una derivación dada en los cuales debeseleccionarse la
producción a ser aplicada. Por lo contrario, los autómatas finitos estudiados hasta ahora son imperativos, en
el sentido que cada transición está únicamente determinada por el estado predecesor y el símbolo de
entrada que ingresa; es decir, no se permite comportamiento alternativo.
Para simplificar el tratamiento de los dos sistemas, vamos a introducir una generalización de aceptor deestados finitos que le otorga naturaleza permisiva. La generalización permite que un dado estado tenga un
número arbitrario de sucesores para un dado símbolo de entrada.
Ejemplo 1:
Esta máquina es permisiva. Si está en el estado A, dos
transiciones son posibles para la entrada "1":
A

B

y

A

C

También se observa que para algunas combinaciones de estados y símbolos de entrada no se especificatransición alguna. Específicamente, A no tiene 0-sucesor y C no tiene 1-sucesor.
Dado que el sucesor de un estado no es siempre único, las transiciones de este aceptor generalizado ya
no pueden ser especificadas por la función f: Q x S → Q. En cambio, debemos especificar qué tripletes del
conjunto Q x S x Q son transiciones de la máquina. Más aún, no vamos a requerir que el estado inicial del
aceptorsea único.
Definición: Un aceptor de estados finitos (AEF) es una tupla de cinco elementos definida como:
M = (Q, S, P, Ι, F)
donde
Q Es el conjunto finito de estados
S
Es el alfabeto finito de entrada
Ι ⊆ Q son los estados iniciales
F ⊆ Q son los estados finales
P ⊆ Q x S x Q es la relación de transición de M
toda vez que (q, s, q') sea un elemento de P, luego q

q' es una transición de M.

Dadoque el comportamiento de un AEF no es necesariamente determinístico, a veces nos referimos a
un AEF como un aceptor de estados finitos no-determinístico.
Las definiciones de s-sucesor, ω-sucesor y secuencia de estados admisibles ya presentadas se aplican
sin inconvenientes a estos aceptores.
Si la relación de transición P de un aceptor de estados finitos es una función, luego cada estado del...