• Author / Uploaded
• Javier Huchin

• Categories
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas
• Lógica
• Ciencia

Citation preview

AUTÓMATAS FINITOS Haciendo una comparación con la rama combinacional de Electrónica Digital, el Álgebra de Boole era la herramienta matemática para poder llevar a cabo la reducción de las fórmu- las lógicas, y por lo tanto, del circuito de conmutación. En el caso de los circuitos secuenciales, esta herramienta no nos basta debido a la dependencia temporal. Por lo tanto, necesitamos otra herramienta para minimizar la dependencia temporal de estos circuitos; esta herramienta es la teoría de autómatas finitos. Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

Definición. En primer lugar, vamos a definir lo que se entiende por autómata finito. Una posible defi- nición de autómata finito es la siguiente: Un autómata finito es un vector de cinco elementos M = (I,S,δ F) donde I es el conjunto finito de entradas, S es el conjunto finito de estados (no vacío), δ es la función de transición de estados y F es el conjunto finito de estados finales (incluidos en S). El hecho de que todos los conjuntos sean finitos, le otorga a este elemento el atributo de finito. También se puede desprender de la definición que un autómata finito es un tipo especial de máquina secuencial, en la cual no existen señales de salida como tal sino que sólo hay señales de entrada y estado, como sucedía en la máquina de Moore. Debido a este motivo, las máquinas secuenciales cumplen todos los axiomas de los autómatas finitos. Siendo ésta la razón por la cual empezaremos el estudio de la teoría desarrollada alrededor de los autómatas finitos. Al igual que en las máquinas secuenciales, la representación de los autómatas finitos puede llevarse a cabo de dos formas diferentes: mediante un diagrama de estados; o mediante una tabla de estados. De estas dos representaciones, la más intuitiva para una traducción partiendo de unas especificaciones de diseño es el diagrama de estados. No obstante, el trabajo con los diagramas de estado no es sencillo ni intuitivo. Por lo tanto, para un posterior procesado utilizaremos la tabla de estados.

Diagramas de Estado. En los diagramas de estado podemos encontrar dos elementos: estados y transiciones. Los estados son las letras o símbolos enmarcados (dentro de un círculo generalmente). En cambio, las transiciones son arcos dirigidos que llevan asociadas una/s etiquetas. Los estados se pueden definir como las posibles situaciones a las que puede llegar el autómata que estemos describiendo. Dentro de estos estados podemos distinguir entre estados estables y estados inestables. Cuando existe alguna transición para la cual se llega al mismo estado desde el que se parte, se dice que es un estado estable. Mientras que si no existe ninguna transición que cumpla la condición anterior, se dice que es un estado inestable. En el caso de la máquina de ventas de refresco, los posibles estados pueden ser: • No hay dinero en el interior de la máquina • Existe el dinero suficiente para sacar un refresco • En el interior de la máquina están cada una de las cantidades permitidas. Por ejemplo si sólo se admiten monedas de 10, 20 y 50 c., el refresco cuesta 60 c. y no se devuelve dinero, las cantidades pueden ser 10, 20, 30, 40, 50 y 60 c. Las transiciones corresponderán a los eventos en las entradas que producirán los cambios de estado en el sentido de la flecha del arco. El cambio de estado se producirá si la condición de entrada coincide con la etiqueta asociada a dicha transición. De nuevo, en el caso de la máquina de refresco, las posibles condiciones de entrada podrían ser: • Introducir las diferentes monedas permitidas: 10, 20 y 50 c. • Pulsar el botón para obtener el refresco. Así pues, una posible parte del diagrama del autómata se puede ver en la figura 2.1:

10 c. 0 c.

10 c.

Figura 2.1.- Porción del diagrama de estado correspondiente a la máquina de refresco. Dicha porción del diagrama se leería del siguiente modo: ... si no hay dinero almacenado en la máquina (estado de 0c.) e introducimos una moneda de 10 c. (evento), pasaremos a la situación de tener almacenado 10 c. (estado de 10c.)... Si realizamos la descripción a través de la tabla de estado, la porción anterior del diagrama se mostraría en la tabla 2.1.

10 c. 10 c.

0 c.

Tabla 2.1. Porción de la tabla de estado correspondiente a la máquina de refresco. Por lo tanto, un posible diagrama de estado para la máquina de refresco se muestra en la figura 2.2. En este diagrama distinguimos 8 situaciones posibles: cada una de las cantidades que se pueden almacenar según las monedas aceptadas (0, 10, 20, 30, 40, 50 y 60 c.); y una situación en la que ya es posible dar el refresco. Los eventos involucrados en dicha máquina serán la inserción de cada una de las monedas (10, 20 y 50 c.), y pulsar el botón de refresco. Las transiciones de estado son las siguientes: • Cuando introduzcamos una moneda, pasaremos al estado con la cantidad actualizada; pero en el caso de que sobrepasemos la cantidad del refresco, nos quedaremos en los 60 c. ya que no se devuelve cambio y no es necesario almacenar dicha cantidad superior. • Cuando pulsemos el botón de refresco, B, no sucederá nada a menos que nos encontremos en el estado de 60 c., en cuyo caso se dará el refresco. B B

0 c. 50 c.

10 c. 20 c. 50 c.

10 c. Refresco

B

B 10 c.

10 c. 20 c.

50 c. 10 c. 20 c. 50 c.

20 c.

50 c. 50 c.

60 c.

10 c. 20 c. 50 c.

20 c. 20 c.

50 c.

20 c.

10 c.

30 c. B 10 c.

B 20 c. 50 c.

B

40 c. 10 c. B

Figura 2.2.- Diagrama de estado correspondiente a la máquina de refresco.

Teoremas y Definiciones. Como nuestro interés está centrado en el análisis y diseño, vamos a orientar los teoremas y definiciones de la teoría de autómatas finitos hacia los sistemas secuenciales. Una vez realizada esta aclaración, en esta teoría encontramos las siguientes definiciones: Equivalencia: Una máquina M es equivalente a otra M*, si para cualquier secuencia de entrada es posible encontrar algún estado inicial tal que la secuencia de salida sea la misma. Esta relación es denotada por M = M*. Compatibilidad: Una máquina M es compatible con otra M*, si para cualquier secuencia de entrada es posible encontrar un estado inicial tal que la secuen- cia de salida sea la misma, siempre y cuando ésta esté especificada. Esta relación se denota por M ~ M*. Máquina completamente especificada: es una máquina en la cual no existen ningún estado total para los que no esté especificada la función de próximo estado y/o de salida. En caso contrario, se dice que la máquina está incompletamente especificada. A continuación vamos a poner ejemplos de máquinas completas e incompletas. una primera máquina podría ser la siguiente: A través de una línea serie va llegando bits, se desea realizar una máquina que indique la llegada de la secuencia 1 -> 0 -> 1. En esta máquina, la señal de entrada es la línea serie mencionada anteriormente, con las posibles combinaciones de ‘1’ y ‘0’. Como ambas combinaciones son posibles, no podemos encontrar ninguna situación de no especificación. Por lo tanto, la máquina será completamente especificada, ya que tanto la salida como los próximos estados deberán estar especificados para todas las secuencias de entradas. Una segunda máquina podría ser la descrita a continuación: La figura 2.3 muestra el esquema de una máquina trituradora. La máquina es cuestión debe gobernar los motores de trituración según las siguientes especificaciones: cuando no exista nada que triturar, los motores deben estar apagados; cuando la máquina esté llena, ambos motores deben estar funcionando; cuando la máquina esté medio vacía, sólo debe funcionar un motor, y en particular aquel que en el estado anterior estuviera apagado (con el fin de garantizar una mayor vida activa de ambos motores).

S1 S2 P M1 M2 Figura 2.3.- Esquema de una máquina trituradora.

Esta máquina es un ejemplo claro de máquina incompleta ya que los sensores de presencia S1 y S2 nunca pueden tener la combinación S1 S2 = “1 0”, ya que es físicamente imposible. Por lo tanto, para esta combinación de entrada, ni la salida ni el próximo estado estarán especificado porque no importará cuales sean al no llegar nunca dicha combinación. No obstante, podemos encontrarnos máquinas en los que la salida sí estará especificada pero el próximo estado no, y viceversa. Según las definiciones de compatibilidad y de equivalencia, se comprueba el siguiente teorema: Teorema 1. Se verifica que si las máquinas M y M* están especificadas de forma: • completa: M = M* M ~ M* • incompleta: M = M* => M ~ M* Demostración.- De las definiciones de equivalencia y compatibilidad se desprende que la primera engloba a la segunda por lo que la dirección hacia la derecha de las implicaciones queda demostrada. En cuanto a la dirección de la izquierda, sólo se puede verificar a priori cuando las dos definiciones sean iguales, caso que sólo se puede dar cuando se trata de máquinas completamente especificadas. Cubrimiento. Una máquina M* cubre a otra M si cualquier secuencia de entrada aplicada a M* produce la misma secuencia de salida que si se aplica a M, siempre y cuando M esté completamente especificada. Esta relación es denotada por M M*. Estados compatibles: Dos estados internos Si y Sj se denominan compatibles, si para cualquier secuencia de entrada, tomando ambos estados como iniciales, las dos secuencias de salida correspondientes resultan idénticas siempre que ambos estados de salida estén completamente especificados. Esta relación es denotada por Si ~ Sj. En caso contrario, los estados se deno- minan incompatibles. La definición de compatibilidad se reduce a comprobar que tienen el mismo valor de salida y sus próximos estados son compatibles para cualquier condición de entrada, ya que la aplicación de la definición de forma directa es invia- ble. Clase de compatibilidad o clases o compatibles: Consiste en un conjunto de estados, los cuales son compatibles dos a dos. Clase máximal o máximo compatible: Será aquella clase que no es un sub- conjunto de ninguna otra clase, y por lo tanto no está contenida totalmente en ninguna otra. Colección de clases cerrada: Es un conjunto de clases, en el cual los próximos estados correspondientes a cada clase están contenidos al menos en una clase de la colección, para cualquier secuencia de entradas. Cubrimiento de una tabla de estados: Se trata de una colección de clases que cubre a una tabla de estados, si cada estado interno de la tabla está con- tenido en una clase de la colección como mínimo.

Autómatas Finitos Deterministas (AFD) Este tipo de autómatas admite su definición de dos maneras bien diferentes:: Como autómatas traductores o reconocedores. La definición como autómatas traductores continua a la definición de las máquinas secuenciales, y se los podría definir como una subclase de estas, ya que los autómatas finitos tendrían como limitante no poder iniciar desde cualquier estado como lo hacen en las máquinas secuenciales. La forma que adoptaremos para la definición de los autómatas finitos deterministas es como autómatas reconocedores, ya que se ajusta con los contenidos de la informática teórica y utilización que se les da dentro del diseño de los analizadores léxicos. Estos autómatas solo se limitarán a aceptar o no una determinada cadena recibida en la entrada, por lo tanto podemos decir que la salida de los mismos solo tendrá dos valores posibles aceptar o no aceptar a la palabra de entrada. Al igual que en las máquinas secuenciales, estos autómatas transitarán entre un conjunto finito de estados posibles, a medida que reciban sucesivamente los caracteres de entrada, en un instante determinado de tiempo el autómata solo podrá estar en uno y solo uno de los estados posibles. Una característica importante de este tipo de autómatas es el determinismo, lo cuál significa que estando en un estado y recibiendo una entrada del exterior el autómata tendrá la posibilidad de transitar a uno y solo un estado del conjunto de estados posibles. Con respecto al conjunto de estados ahora se pueden clasificar en tres tipos: Estado Inicial, que es pon donde comenzará la ejecución de la máquina; Estados finales o de aceptación que será un subconjunto del conjunto de estados por los que transitará la máquina, y si cuando se hayan terminado de procesar todos los símbolos de entrada y no reste ningún símbolo por leer, la máquina quede posicionada en uno de estos estados de aceptación, se concluirá que la cadena procesada será aceptada por el autómata. y Estados Intermedios, que tienen comportamiento idéntico a los definidos en las máquinas secuenciales.

1.

Definición:

2. Los autómatas finitos deterministas quedarán formalmente definida mediante una quíntupla como sigue: AFD = ( ∑ , Q, q0, F, f ) donde:

∑

Alfabeto de símbolos de entrada.

Q

Conjunto finito de estados

q0

q0

F

F Q - es el conjunto de estado finales de aceptación.

f

Función de transición de estados definida como

Q – estado inicial previsto

f: Q x ∑

Q

3.

Interpretación de funcionamiento:

Este autómata recibirá una cadena en la cinta de entrada e ira procesando de uno a la vez los símbolos de entrada. Comenzará su funcionamiento posicionada en el estado inicial, y desde este estado comenzará su ejecución. En cada intervalo de tiempo discreto realizará dos acciones las cuales serán consideradas como acciones indivisibles en un determinado intervalo de tiempo. Las acciones que realiza son: ·

Leer el próximo símbolo, desde la cinta de entrada.

·

Transitar, cambiar de estado

4.

Extensión a palabras

El autómata finito determinista realizará transiciones de estados a través de la función f solo cuando reciba un símbolo de entrada. Esto puede generalizarse a una palabra completa, o cuando reciba la palabra vacia, en este caso se denominará una función de transición f´ como la función f´ : Q x ∑*

Q

Donde: f´ (q, ax) = f´(f(q,a),x) f´ (q,

)= q

con a

5.

∑;x

∑* ; q

Q

Aceptación de Palabras:

Una palabra será aceptada por un AFD si estando formada pos símbolos pertenecientes al alfabeto de entrada, al finalizar de procesar la misma, el autómata queda posicionado en una de los estados perteneciente al conjunto de estados finales de aceptación.

Dada: x W(∑) f ( q0, x) = qn Si qn

6.

F la cadena x es aceptada

Lenguaje reconocido por un AFD:

Es el conjunto de todas las palabras reconocidas por el Autómata Finito Determinista.

L AFD = { x / x

∑* y f ( q0, x) = qn con qn

F}

7.

Ejemplo:

Dado el siguiente AFD definido como:

AFD1 = ( ∑, Q, qi, F, f ), donde: ∑= { 0,1 } (Conjunto de símbolos de entrada del AFD) Q= { p, q, r } (Conjunto de estados del AFD) qi = p (estado inicial del AFD (p Є Q)) F= {q } (Conjunto de estados de aceptación del AFD ({q } с Q)) f: función de transición de estados del AFD Donde la función f será:

*

f

0

1

También puede expresarse como:

p

q

r

f(p, 0)= q

f(p, 1)= r

q

r

q

f(q, 0)= p

f(q, 1)= q

r

r

r

f(r, 0)= r

f(r, 1)= r

Representando su comportamiento por medio del grafo dirigido:

En donde el lenguaje aceptado por esta AFD será:

L AFD1 = {x / x

∑* y x = 0.1n con n

N

0}

8.

Accesibilidad entre estados (A)

Dados dos estados dentro de un autómata, se dice que uno de los estado es accesible desde el otro, si existe una palabra x formada por símbolos del alfabeto de entrada que hace que partiendo de este estado y a través de la aplicación de la función de transición se pueda llegar hasta el otro. De esta manera definiremos: Sean p y q existe x

Q dos estados dentro de un AFD y W(∑) tal que:

f´( q , x ) = p Entonces se dice que: pAq ( Se lee – p es accesible desde q )

9.

Conjunto Conexo

Un conjunto conexo es aquel en donde todos sus estados son accesibles desde el estado inicial. Por lo tanto un AFD será conexo si todo estado perteneciente al conjunto de estados es accesible desde el estado inicial. Si en un AFD existieran estados que no son accesibles desde el estado inicial, los mismos pueden ser eliminados, de manera de simplificar el autómata. Esta eliminación no afectará al comportamiento y por lo tanto continuará aceptando el mismo Lenguaje. Ejemplo de conjunto conexo: Dado el siguiente AFD definido como: AFD1 = ( ∑, Q, qi, F, f ), donde: ∑= { 0,1 } Q= { p, q, r , t, s } qi = p F= {q ,s } Donde la función f será:

*

F

0

1

También puede expresarse como:

p

q

r

f(p, 0)= q

f(p, 1)= r

q

r

q

f(q, 0)= p

f(q, 1)= q

R

r

r

f(r, 0)= r

f(r, 1)= r

T

s

q

f(t, 0)= s

f(t, 1)= q

*

s

s

t

f(s, 0)= s

f(s, 1)= t

El Grafo correspondiente será:

Analizando, el grafo del AFD, vemos que alos estados t y s , es imposible acceder desde el estado inicial p, por lo tanto estos estados pueden ser eliminados del AFD y el comportamiento del autómata no se alterará.

10.

Equivalencias en los AFD

A continuación presentaremos definiciones de equivalencias para culminar con equivalencia entre Autómatas Finitos Deterministas. Equivalencias entre estados: Dos estados p y q serán equivalentes si: Para toda cadena “ x ” que desde el estado p hace transitar el autómata hasta un estado de aceptación, también lo hace desde el estado q. Debiendo ocurrir simultaneamente que para toda otra cadena “ y “ que no hacen transitar desde el estado p hasta un estado de aceptación, tampoco lo hará desde el estado q. De esta manera definiremos: Sean p y q

Q dos estados dentro de un AFD

p E q ( Se lee: p y q son equivalentes)

si cadena x W(∑) - se puede alcanzar un estado final previsto tanto comenzando desde el estado p como el de q Y otra cadena y W(∑) – no se puede alcanzar un estado final previsto tanto comenzando desde el estado p como el de q.

2.

Autómatas Finitos No Deterministas (AFND)

Definición: Un Autómata finito determinista queda definido por un quíntupla, al igual que en los AFD, y que su diferencia fundamental se encuentra, en como se definirá a la función de transición:

AFND = ( ∑ , Q, q0, F, f ) donde:

∑

Alfabeto de símbolos de entrada.

Q

Conjunto finito de estados

q0

qo

F

F Q - es el conjunto de estado finales de aceptación.

f

Función de transición de estados definida como

Q – estado inicial previsto

f: Q x (∑ U {

} ) → P (Q)

En donde P (Q), es el conjunto que se puede armar con todos los subconjuntos de Q Este tipo de autómatas se diferencia de los AFD, básicamente en como puede constituirse la función de transición:. Esta diferencias son las siguientes:

1)

Para cada par estado entrada, el autómata puede tener la posibilidad de transitar a mas de un estado posible.

2)

Para algún par de estado entrada, el autómata puede no tener definido ninguna transición. Lo que significa que podrá realizar transición alguna.

3)

Puede realizar transiciones de un estado a otro sin leer símbolo alguno de la entrada. A este tipo particular de transiciones se las denomina transiciones- .

Ejemplo: Una AFND puede definirse como sigue:

AFND1 = ( { 1 , 0 }, { p, q , r, s , t }, p, { r, t }, f ) , donde: la función f puede definirse: En forma explicita:

f (p,0) = r

f (q,1) = {s,r}

f (p,1) = {t,s}

f (r,0) = p

f (t,

f (s,0) = {p,r}

f (p, ) = t

f (s,1) = t

)=s

f (t,1) = s

Tabla de doble entrada: Al igual que en los AFD tendremos:

· En las filas los estados · si el estado es final lo antecederá un * · si el estado es inicial lo marcaremos con una → · En las columnas se pondrán los símbolos del alfabeto de entrada y se añadirá una columna adicional para · En la intersección (celdas de la matriz) se indicarán las transiciones

f

0

1

p

r

{t,s}

q

{s,r}

r

p

s

{p,r}

t

t

t

s

s

En la tabla f de la función de transición, se encuentran presentes las tres situaciones que se admiten en los AFND a diferencia de los AFD. La situación identificada como de no determinismo propiamente dicho, en donde para un estado determinado y ante una misma entrada, el autómata tiene la posibilidad de transitar a uno o mas estado. Esta situación se presenta en tres oportunidades: f (p,1) = {t,s} f (q,1) = {s,r} f (s,0) = {p,r}

y en representación gráfica de f (p,1) = {t,s} sería:

La segunda situación cuando que es no tiene definida transición a estado alguno se presenta en las siguientes situaciones:

f (q,0) = f ( r,1) = f ( t,0) = Y la tercer situación es cuando tiene la posibilidad de transitar de estado, aún sin leer ningún símbolo de la entrada, esta situación se evidencia en las siguientes situaciones:

f (p, ) = t f (t, ) = s

Gráficamente se evidencia f (p, ) = q de la siguiente manera:

Diagrama de transiciones:

·

Cada Nodo es un estado

·

El estado inicial tendrá un arco entrante no identificado

·

Los estados finales tendrán doble círculo.

·

Existirá un arco con sentido, etiquetado con un símbolo a entre dos nodos p y q si existe una transición F(p,a) = q.