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

...