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

...