Práctica de FSM (Ingeniería I)

Ejercicio 07

Modele con FSMs el siguiente protocolo “Acelerador de Peticiones”.

El acelerador media entre un cliente y dos servidores. En un escenario normal, el acelerador recibe la petición del cliente y lo envía a ambos servidores. La primera respuesta que reciba es la que enviará al cliente, ya que los dos servidores otorgan el mismo servicio, contestan indefectiblemente y devuelven exactamente el mismo resultado, pero uno puede ser más rápido que el otro en distintas situaciones. El acelerador luego se encarga de cancelarle la petición al otro servidor, para que no siga trabajando y asegurarse que no le responda. El cliente no puede hacer otra petición hasta que no reciba la respuesta del acelerador. El cliente nunca debe recibir una respuesta atrasada de una petición anterior. Suponer que no se pierden paquetes en ninguna comunicación.

FSM Cliente:

<graphviz>
digraph G {
	// Config
	rankdir=LR;
	size="8,6";
	node [style=rounded, fontname=Arial, fontsize=10];
	edge [fontname=Arial, fontsize=10];	
	
	// Estados
	Inicial;
	Esperando;
	// Transiciones
	Inicial->Esperando [label="Pedir!"];
	Esperando->Inicial [label="ResponderCliente?"];
}
</graphviz>

FSM Servidor i = {1,2}:

<graphviz>
digraph G {
	// Config
	rankdir=LR;
	size="8,6";
	node [style=rounded, fontname=Arial, fontsize=10];
	edge [fontname=Arial, fontsize=10];	
	
	// Estados
	Inicial;
	Procesando;
	// Transiciones
	Inicial->Procesando [label="PedirServidor?"];
	Procesando->Inicial [label="Responder i!"];
	Procesando->Inicial [label="Cancelar i?"];
}
</graphviz>

FSM Acelerador:

<graphviz>
digraph G {
	// Config
	//rankdir=LR;
	size="8,6";
	node [style=rounded, fontname=Arial, fontsize=10];
	edge [fontname=Arial, fontsize=10];	
	
	// Transiciones
	Inicial->Pedido [label="Pedir?"];
	Pedido->Enviado [label="PedirServidor!"];
	Enviado->Respondio1 [label="Responder 1?"];
	Enviado->Respondio2 [label="Responder 2?"];
	Respondio1->Listo [label="Cancelar 2!"];
	Respondio2->Listo [label="Cancelar 1!"];
	Listo->Inicial [label="ResponderCliente!"];
}
</graphviz>

Composicion:

Protocolo Acelerador de Peticiones = Acelerador || Servidor 1 || Servidor 2 || Cliente

Ejercicio 08

Modele mediante una FSM temporizada un semáforo con interruptor que presente las siguientes características:

• La luz verde dura 30 segundos.
• La luz amarilla dura 5 segundos.
• La luz roja dura a lo sumo 30 segundos.
• Si la luz roja ha estado prendida por más de 20 segundos y se oprime el interruptor, no se produce ningún efecto.
• Si la luz roja ha estado prendida a lo sumo 20 segundos y se oprime el interruptor, la luz cambia a verde en 10 segundos más.
• Si el interruptor es oprimido cuando la luz verde o amarilla está encendida, el semáforo lo ignora.

FSM Semaforo:

<graphviz>
digraph G {
	// Config
	size="8,6"
	node [style=rounded, fontname=Arial, fontsize=10];
	edge [fontname=Arial, fontsize=11];	
	// Estados
	Verde [label="Verde\n[tVerde < 30]"];
	AmarillaR [label="AmarillaRoja\n[tAmarillo < 5]"];
	AmarillaV [label="AmarillaVerde\n[tAmarillo < 5]"];
	RojaOprimido [label="RojaOprimido\n[tRojo < 10]"];
	Roja [label="Roja\n[tRojo < 30]"];
	// Oprimir
	Verde->Verde [label="Oprimir?"];
	AmarillaR->AmarillaR [label="Oprimir?"];
	AmarillaV->AmarillaV [label="Oprimir?"];
	RojaOprimido->RojaOprimido [label="Oprimir?"]
	Roja->Roja [label="Oprimir?\n[tRoja > 20]"]
	Roja->RojaOprimido [label="Oprimir?\n[tRoja > 20]\n{tRoja}"]
	// Pasa tiempo
	AmarillaR->Roja [label="PasaARoja\n[tAmarillo = 5]\n{tRoja}"];
	Roja->AmarillaV [label="PasaDeRoja\n[tRoja = 30]\n{tAmarilla}"];
	RojaOprimido->AmarillaV [label="PasaDeRojaOprimido\n[tRoja = 10]\n{tAmarilla}"];
	AmarillaV->Verde [label="PasaAVerde\n[tAmarillo = 5]\n{tVerde}"];
	Verde->AmarillaR [label="PasaDeVerde\n[tVerde = 30]\n{tAmarilla}"];
}
</graphviz>

FSM Interruptor:

<graphviz>
digraph G {
	// Config
	size="10"
	node [style=rounded, fontname=Arial, fontsize=10];
	edge [fontname=Arial, fontsize=11];	
	// Grafo
	Boton;
	Boton->Boton [label="Oprimir!"];
}
</graphviz>

Variables:

• tVerde: timer
• tAmarillo: timer
• tRojo: timer

Composicion:

Semaforo con Interruptor = Interruptor || Semaforo

Ejercicio 10

Se desea modelar con FSM una simplificación de un teléfono celular que responde a la siguiente descripción:

El teléfono posee teclado, display numérico y una tapa que cubre el teclado. El teclado está formado por los botones 0 al 9, on, send, end y clear. El display puede mostrar hasta 8 dígitos. Se enciende al presionar on. La tecla clear borra todo el número ingresado. Una vez que se ingresó el número deseado, presionando send se inicia la conversación, la cual se mantiene hasta que se cierre la tapa, se presione end o se apague el teléfono con on. Al abrir la tapa, el número del display es el que figuraba al momento de cerrarla o apagar el teléfono.

Asuma cualquier aspecto del funcionamiento de este aparato que no esté explicado en el enunciado, documentando claramente lo que Ud. asuma.

FSM Teléfono Celular

<graphviz>
digraph G {
	// Config
	size="8,6"
	node [style=rounded, fontname=Arial, fontsize=8];
	edge [fontname=Arial, fontsize=9];

	// Estados
	ApagadoCerrado [label="Apagado y\nCerrado"];
	ApagadoAbierto [label="Apagado y\nAbierto"];
	PrendidoAbierto [label="Prendido y\nAbierto"];
	PrendidoCerrado [label="Prendido y\nCerrado"];
	Hablando [label="Hablando"];

	// Cambios de estado
	ApagadoCerrado->ApagadoAbierto [label="Abrir"];
	ApagadoAbierto->ApagadoCerrado [label="Cerrar"];
	ApagadoAbierto->PrendidoAbierto [label="On\n{i=0, n=0}"];
	PrendidoAbierto->ApagadoAbierto [label="On"];
	PrendidoAbierto->PrendidoCerrado [label="Cerrar"];
	PrendidoAbierto->Hablando [label="Send"];
	PrendidoCerrado->PrendidoAbierto [label="Abrir"];
	Hablando->PrendidoAbierto [label="End"];
	Hablando->PrendidoCerrado [label="Cerrar"];
	Hablando->ApagadoAbierto [label="On"];

	// Invalidos de Apagado y Abierto
	ApagadoAbierto->ApagadoAbierto [label="Clr"];
	ApagadoAbierto->ApagadoAbierto [label="0"];
	ApagadoAbierto->ApagadoAbierto [label="..."];
	ApagadoAbierto->ApagadoAbierto [label="9"];
	ApagadoAbierto->ApagadoAbierto [label="End"];
	ApagadoAbierto->ApagadoAbierto [label="Send"];

	// Invalidos de Hablando
	Hablando->Hablando [label="Clr"];
	Hablando->Hablando [label="0"];
	Hablando->Hablando [label="..."];
	Hablando->Hablando [label="9"];
	Hablando->Hablando [label="Send"];

	// Invalidos de Prendido y Abierto
	PrendidoAbierto->PrendidoAbierto [label="0\n[i>8]"];
	PrendidoAbierto->PrendidoAbierto [label="..."];
	PrendidoAbierto->PrendidoAbierto [label="9\n[i>8]"];

	// Validos de Prendido y Abierto
	PrendidoAbierto->PrendidoAbierto [label="0\n[i<=8]\n{n[i]=0, i++}"];
	PrendidoAbierto->PrendidoAbierto [label="..."];
	PrendidoAbierto->PrendidoAbierto [label="0\n[i<=8]\n{n[i]=9, i++}"];
	PrendidoAbierto->PrendidoAbierto [label="Clr\n{i=1, n[]=0}"];
}
</graphviz>

Variables:

• i:[1..8]
• n[1..8]:[0..9]

Ejercicio 11

(Hecho en clase)

Ejercicio 12

Ver [Link a PDF]

Ejercicio 13

Cansados de ver como continuamente se desvirtúa el mundialmente famoso "Piedra, Papel o Tijera", científicos de una sociedad secreta del sur de Suecia, se han puesto cómo objetivo formalizar el citado juego, cambiando algunas de sus reglas e introduciendo reglas nuevas.

Algunas de sus conclusiones son:

• El juego posee dos jugadores y un árbitro.
• Se juega al mejor de 3: el primer jugador en ganar dos partidas, gana el juego.
• La dinámica es manejada por el árbitro.

Cada partida se inicia cuando los tres (el árbitro y los 2 jugadores) gritan "Piedra", "Papel", "o Tijera". Entre cada una de las palabras, el árbitro y los jugadores toman acciones distintas:

• En el caso de los jugadores, agitan sus manos de alguna forma (usualmente de arriba hacia abajo, con el puño cerrado).
• En el caso del árbitro, grita una frase de aliento como "Vamos nene!", "Vos podés!", "Que no decaiga!", etc.

Inmediatamente después de decir "o Tijera”, cada uno de los jugadores debe hacer una elección entre alguno de los 3 elementos. El árbitro debe determinar el ganador de la partida según el siguiente criterio:

• Tijera le gana a Papel.
• Papel le gana a Piedra.
• Piedra le gana a Tijera.

En caso de compartir la elección, el resultado es empate y la partida se debe jugar nuevamente. Luego el árbitro indica a cada jugador si ganó o perdió y el que ganó ríe y el que perdió llora. Los jugadores no saben si ganan o pierden (es como si no vieran a su rival).

Si la competencia aún no terminó, el árbitro indica que se jugará una nueva partida. En caso de que la competencia haya terminado, el árbitro le indicará al jugador correspondiente, este gritará "Iuupiii!" y quedará listo para jugar una nueva competencia.

Formalice las conclusiones de los científicos, utilizando FSMs.

FSM Arbitro:

<graphviz> digraph G { // Config size="12,10"; node [style=rounded, fontname=Arial, fontsize=10]; edge [fontname=Arial, fontsize=10];

// Estados Inicial->Comienzo [label="Nuevo Juego!"]; Comienzo->GritoPiedra [label="Piedra!"]; GritoPiedra->HagoPiedra [label="AlientoPiedra"]; HagoPiedra->GritoPapel [label="Papel!"]; GritoPapel->HagoPapel [label="AlientoPapel"]; HagoPapel->GritoTijera [label="Tijera!"]; GritoTijera->Eligieron [label="Muestra?"]; Eligieron->Comienzo [label="Empate!\n[elem1 = elem2]"]; Eligieron->Declarar [label="Gano 1!\n[gana(elem1,elem2)]\n{wins1++}"]; Eligieron->Declarar [label="Gano 2!\n[gana(elem2,elem1)]\n{wins2++}"]; Declarar->Inicial [label="Campeon 1!\n[wins1 = 2]\n{wins1 = wins2 = 0}"]; Declarar->Inicial [label="Campeon 2!\n[wins2 = 2]\n{wins1 = wins2 = 0}"]; Declarar->Comienzo [label="OtraPartida!\n[wins1 < 2 && wins2 < 2]"];

} </graphviz>

FSM Jugador i = {1,2}:

<graphviz> digraph G { // Config size="14,12"; node [style=rounded, fontname=Arial, fontsize=10]; edge [fontname=Arial, fontsize=10];

// Transiciones Inicial->Comienzo [label="Nuevo Juego?"]; Comienzo->GritoPiedra [label="Piedra?"]; GritoPiedra->HagoPiedra [label="MuevoManoPiedra i"]; HagoPiedra->GritoPapel [label="Papel?"]; GritoPapel->HagoPapel [label="MuevoManoPapel i"]; HagoPapel->GritoTijera [label="Tijera?"]; GritoTijera->Elige [label="ElijoPie i\n{elemi = pie}"]; GritoTijera->Elige [label="ElijoPap i\n{elemi = pap}"]; GritoTijera->Elige [label="ElijoTij i\n{elemi = tij}"]; Elige->Eligio [label="Muestra!"]; Eligio->Comienzo [label="Empate?"]; Eligio->Gane [label="Gano i?"]; Eligio->Perdi [label="Gano op(i)?"]; Gane->FinPartida [label="Rio i"]; Perdi->FinPartida [label="Lloro i"]; FinPartida->GaneCompetencia [label="Campeon i?"]; GaneCompetencia->Inicial [label="Grito Iupi"]; FinPartida->Inicial [label="Campeon op(i)?"]; FinPartida->Comienzo [label = "OtraPartida?"]; } </graphviz>

Variables:

• elem1: string
• elem2: string
• wins1: int
• wins2: int

Macros:

• gana(e1, e2) = (e1 = tij && e2 = pap) || (e1 = pap && e2 = pie) || (e1 = pie && e2 = tij)
• op(i) = i%2 + 1

Composicion:

PiedraPapelTijera = Arbitro || Jugador1 || Jugador2

Ejercicio 14

Ver Resuelto de Parcelas.