Maquinas De Estados Finitos

Máquinas de Estado Finito Ingeniería de Software I

- 1 -

Máquinas de Estado Finito

INTRODUCCIÓN ................................................................................................................ 2

SINTAXIS.............................................................................................................................. 2

SEMÁNTICA........................................................................................................................ 3

EJEMPLO .............................................................................................................................. 3

TRAZAS ................................................................................................................................ 4

EJEMPLO .............................................................................................................................. 4

DEADLOCK ......................................................................................................................... 5

EJEMPLO .............................................................................................................................. 5

SEMÁNTICA DEL DEADLOCK ................................................................................................ 5

COMPOSICIÓN DE FSM................................................................................................... 6

SINTAXIS DE LA COMPOSICIÓN ............................................................................................. 7

Ejemplo ........................................................................................................................... 7

Sobre la composición...................................................................................................... 8

EJEMPLO .............................................................................................................................. 9

EXTENSIONES.................................................................................................................. 10

CONDICIONES .................................................................................................................... 10

ACCIONES .......................................................................................................................... 10

VARIABLES ........................................................................................................................ 10

Ejemplo ......................................................................................................................... 11

CONDICIONES DE SALIDA DE UN ESTADO ........................................................................... 11

Ejemplo ......................................................................................................................... 12

FSMS TEMPORIZADAS....................................................................................................... 12

Ejemplo ......................................................................................................................... 13

NO DETERMINISMO....................................................................................................... 13

EJEMPLO ............................................................................................................................ 13

MODELO CONCEPTUAL ............................................................................................... 17

EJEMPLO ............................................................................................................................ 17

ACLARACIONES ................................................................................................................. 20

Máquinas de Estado Finito Ingeniería de Software I

- 2 -

Introducción

Las máquinas de estado finito son una herramienta muy útil para especificar aspectos relacionados con tiempo real, dominios reactivos o autónomos, computación reactiva, protocolos, circuitos, arquitecturas de software, etc.

El modelo de FSM (Finite State Machine) es un modelo que posee sintaxis y semántica formales y que sirve para representar aspectos dinámicos que no se expresan en otros diagramas.

Sintaxis

Las máquinas de estado finito se definen como una tupla S , Σ, A ⊆ S Σ S , sk , donde:

• S  s1 , s2 ,..., sm : es un conjunto finito de nodos.

• Σ : es un alfabeto finito de etiquetas.

• A: es un conjunto finito de aristas etiquetadas que unen nodos.

• sk ∈ S : es el estado inicial.

Ejemplo

a

2

1

b b

3

a

• 〈 S  1,2,3 ,

• Σ  a , b ,

• A  1, a ,2  ,  2, b,3  ,  3, a ,1 , 1, b,3 ,

• sk 1 〉

Vale la pena destacar que formalmente la máquina de estado es la tupla anterior y no el “dibujo”. Este es tan sólo una representación gráfica de la máquina de estado para tener una más sencilla y rápida visualización de su contenido.

Máquinas de Estado Finito Ingeniería de Software I

- 3 -

Semántica

Los nodos representan los posibles estados de aquello que se desea modelar. Las etiquetas representan eventos que provocan un cambio. Las aristas determinan de qué manera cada estado, dado un evento, deriva en otro estado.

Ejemplo

Supongamos que se quiere modelar el comportamiento de una puerta. La puerta, inicialmente cerrada, puede pasar a estar abierta tras el evento “abrir puerta”. Una vez abierta, puede pasar al estado cerrada, tras el evento “cerrar puerta”.

abrir puerta

cerrada abierta

cerrar puerta

Máquinas de Estado Finito Ingeniería de Software I

- 4 -

Trazas

El conjunto de posibles trazas correspondientes a una máquina de estado finitos, se puede definir en término de grafos, cómo el conjunto de todos los caminos (de ejes) alcanzables desde el estado inicial.

Ejemplo

Dada la FSM de ejemplo:

a

2

1

b b

3

a

Las trazas de esta FSM son:

• {a, b, a} correspondiente a 1, 2, 3, 1

• {b, a} correspondiente a 1, 3, 1

• {a, b, a, b, a} correspondiente a 1, 2, 3, 1, 3, 1

• {b, a, a, b, a} correspondiente a 1, 3, 1, 2, 3, 1

• {b, a, b, a, ... , b, a} 1, 3, 1, 3, …, 1, 3

• Etc…

Máquinas de Estado Finito Ingeniería de Software I

- 5 -

Deadlock

Formalmente hablando, una FSM S , Σ, A ⊆ S  S , sk , tiene deadlock, si existe algún

nodo s ∈ S , tal que no existen un evento e y un nodot ∈ S tal que s , e, t  ∈ A. En otras

palabras, si existe algún nodo que no posea “salida” para ningún evento.

Ejemplo

El estado 2 no posee salida alguna.

a

2

1

b

3

a

Semántica del deadlock

La existencia de deadlock no necesariamente habla de un mal modelado. Más adelante veremos que puede ser un efecto no deseado de la composición de FSMs.

Un ejemplo en donde el deadlock no necesariamente “está mal”, podría ser el siguiente: Queremos modelar un partido de fútbol. Un partido de fútbol, en particular, se organiza, se juega y finaliza. Y una vez finalizado, ese partido no se juega ni organiza nunca más. Entonces podríamos modelarlo de la siguiente manera:

árbitro pita comienzo del partido árbitro pita fin del partido

Esperando Partido en Partido

curso finalizado

inicio

Máquinas de Estado Finito Ingeniería de Software I

- 6 -

Composición de FSM

Supongamos que se quiere modelar el siguiente comportamiento de un horno microondas: El horno microondas posee una puerta. Si la puerta está cerrada, entonces puede estar o no en funcionamiento (según se prenda o apague). Estando prendido no es posible abrir la puerta del horno sin antes apagarlo.

También asumamos lo siguiente: en cualquier momento es posible establecer el modo de cocción.

modo de cocción

modo de

cerrar puerta

cocción

Puerta abierta y encendido deshabilitado

Puerta cerrada y horno apagado

prender horno apagar horno

abrir puerta

Puerta cerrada y horno prendido

modo de cocción

No es obligatorio etiquetar los nodos,

...