Formal Methods for Software Development | TDA294/DIT271, LP1, HT2020 | |||||||||
Channels and Linear Temporal LogicThe solutions to exercises 1--4 can be found here. Exercise 1Channels are useful when modelling distributed systems. In Promela a channel has a capacity and a message type. chan myChan = [0] of { byte } This simple example specifies a channel called myChan with 0 capacity, making it a rendezvous channel. The messagetype in this case is byte. Now create two processes. The first process sends the numbers 0 through 9 onto the channel. The second process reads the values of the channel and outputs them. Exercise 2Is it possible that process p does not read from the channel at all? chan com = [0] of {byte} byte value = 0; proctype p() { byte i = 0; do :: if :: i >= 5 -> break :: else -> printf("Doing something else\n"); i ++ fi :: com ? value ; printf("p received: %d\n",value) od } init { atomic { run p() } end: com ! 100; } Exercise 3Model a system having 5 clients and 2 servers where a client cannot send another request before their previous one was processed by a server. The suggested solution uses buffered channels and describes the behaviour of the server processes. Complete the solution for the client processes. chan request = [2] of { byte, chan}; chan reply[5] = [2] of { byte }; active [2] proctype Server() { byte client; chan replyChannel; do :: request ? client, replyChannel -> printf("Client %d processed by server %d\n", client, _pid); replyChannel ! _pid od } proctype Client(byte id) { ... } init { ... } Exercise 4Model an office where two computer systems are hooked up to a single printer. Model the computer systems such that they have mutual exclusion on the printer. The printer can be modeled as the number of jobs it has. The two systems can communicate with each other via a rendezvous channel. Verify that it is never the case that both systems print at the same time. Exercise 5Consider a crossing of two streets with one traffic light (nr 1) controlling the north-to-south direction and one (nr 2) for the west-to-east direction. Assume you have the following propositional variables: R1 (traffic light 1 is red), G1 (traffic light 1 is green), R2 (traffic light 2 is red), G2 (traffic light 2 is green). Give LTL formulas formalising the following properties:
Answers:
Comment for exercise 6+7+8If you want, you can use GOAL to check your own solutions. With GOAL you can
If everything is fine, a dialog pops up telling that they are equivalent; otherwise, the dialog shows you a counterexample. IMPORTANT NOTE: As mention earlier the program has a different way to label the transitions. Refer to the documentation (Help -> Help contents) to understand in what they differ. Exercise 6Which language is accepted by the following Büchi automata?
Exercise 7Consider the following LTL formulas and their corresponding Büchi automata. State whether these formulas accept the same language or not. If not, provide a counter-example in the form of a word which is accepted by the LTL formula but not by the automaton, or vice versa.
Answers:
Exercise 8Consider the largest language formed with the Vocabulary V={a,b,c} such that for each word of the language the following holds:
Build a Büchi automaton that corresponds to it. Answer: ![]() | ||||||||||
W. Ahrendt, Sep 20, 2020 |