Introducci N A Los Sistemas Aut Matas Completo
Páginas: 24 (5785 palabras)
Publicado: 11 de agosto de 2015
TEMA II: INTRODUCCIÓN A LA TEORÍA DE 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órmulas 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. Porlo tanto, necesitamos otra herramienta para minimizar la dependencia
temporal de estos circuitos; esta herramienta es la teoría de autómatas finitos.
1. Introducción. Definición.
En primer lugar, vamos a definir lo que se entiende por autómata finito. Una posible definición de autómata finito es la siguiente:
Un autómata finito es un vector de tres elementos
M = (I,S,δ, F)
donde I es el conjuntofinito 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 noexisten 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 losautó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 procesadoutilizaremos la tabla de estados.
10
Dpto. Ingeniería Electrónica de Sistemas Informáticos y Automática
2. 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 sepueden 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, sedice 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, lascantidades 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...
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órmulas 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. Porlo tanto, necesitamos otra herramienta para minimizar la dependencia
temporal de estos circuitos; esta herramienta es la teoría de autómatas finitos.
1. Introducción. Definición.
En primer lugar, vamos a definir lo que se entiende por autómata finito. Una posible definición de autómata finito es la siguiente:
Un autómata finito es un vector de tres elementos
M = (I,S,δ, F)
donde I es el conjuntofinito 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 noexisten 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 losautó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 procesadoutilizaremos la tabla de estados.
10
Dpto. Ingeniería Electrónica de Sistemas Informáticos y Automática
2. 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 sepueden 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, sedice 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, lascantidades 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...
Leer documento completo
Regístrate para leer el documento completo.