• Non ci sono risultati.

Course “Formal Methods” TEST

N/A
N/A
Protected

Academic year: 2021

Condividi "Course “Formal Methods” TEST"

Copied!
11
0
0

Testo completo

(1)

Roberto Sebastiani

DISI, Universit` a di Trento, Italy June 17

th

, 2021

769857918 Name (please print):

Surname (please print):

(2)

Given the following OBDD, with the ordering { A5, A1, A3, A2, A4},

A5

A3

A2

A4

A1

for each of the following Boolean formulas, say whether the OBDD represents it or not.

(a) (¬A5 → (¬A1 → (¬A3 → (¬A2 → A4)))) (b) ( A2∨ A1∨ A5∨ A3∨ A4)

(c) ( A3∧ A5∧ A4∧ A1∧ A2)

(d) ( A5 → ( A1 → ( A3 → ( A2 → ¬A4))))

[SCORING [0...100]:

• +25pts for each correct answer

• -25pts for each incorrect answer

• 0pts for each unanswered question

(3)

Consider the following Kripke Model M :

p, ¬q s

3

¬p, q s

0

p, q s

1

For each of the following facts, say if it is true or false in LTL.

(a) M |= GFp (b) M |= FG¬p (c) M |= pUq

(d) M |= (GF¬p ∧ GF¬q) → p

[SCORING [0...100]:

• +25pts for each correct answer

• -25pts for each incorrect answer

• 0pts for each unanswered question ]

(4)

Consider the following fair Kripke Model M :

F1 F2

p, ¬q s

3

¬p, q s

0

p, q s

1

For each of the following facts, say if it is true or false in LTL.

(a) M |= GFp (b) M |= FG¬p (c) M |= pUq

(d) M |= (GF¬p ∧ GF¬q) → p

[SCORING [0...100]:

• +25pts for each correct answer

• -25pts for each incorrect answer

• 0pts for each unanswered question ]

(5)

For each of the following fact regarding Buchi automata, say if it true or false.

(a) The following BA represents FGq:

q q

q

(b) The following BA represents FGq:

q q

q

(c) The following BA represents pUq:

p

p q

q

(d) The following BA represents pUq:

p

p q

q

[SCORING [0...100]:

• +25pts for each correct answer

• -25pts for each incorrect answer

• 0pts for each unanswered question ]

(6)

Consider the following pair of ground and abstract machines M and M: M :

MODULE main VAR

v1 : boolean;

v2 : boolean;

v3 : boolean;

ASSIGN

init(v1) := FALSE;

init(v2) := TRUE;

init(v3) := FALSE;

TRANS

(next(v1) <-> v2) &

(next(v2) <-> v3) &

(next(v3) <-> v1)

M:

MODULE main VAR

v1 : boolean;

v2 : boolean;

v3 : boolean;

ASSIGN

init(v1) := FALSE;

init(v2) := TRUE;

TRANS

(next(v1) <-> v2) &

(next(v2) <-> v3)

For each of the following facts, say which is true and which is false.

(a) M simulates M . (b) M simulates M.

(c) For every Boolean property φ on v1,v2, if M |= Gφ, then M |= Gφ, (d) For every Boolean property φ on v1,v2, if M |= Gφ, then M |= Gφ,

[SCORING [0...100]:

• +25pts for each correct answer

• -25pts for each incorrect answer

• 0pts for each unanswered question ]

(7)

Consider the following piece of a much bigger formula, which has been fed to a CDCL SAT solver:

c1 :¬A9∨ A12∨ ¬A1

c2 : A9∨ ¬A7∨ ¬A3

c3 :¬A11∨ A5∨ A2

c4 :¬A10∨ ¬A12∨ A11

c5 :¬A11∨ A6∨ A4

c6 :¬A9∨ A10∨ ¬A1

c7 : A9∨ A8∨ ¬A3

c8 :¬A5∨ ¬A6

c9 : A7∨ ¬A8∨ A13

...

Suppose the solver has decided, in order, the following literals (possibly interleaved by others not occurring in the above clauses):

{..., A1, ...¬A2, ...¬A4, ... A3, ...¬A13, ..., A9}

(a) List the sequence of unit-propagations following after the last decision, each literal tagged (in square brackets) by its antecedent clause

(b) Derive the conflict clause via conflict analysis by means of the 1st-UIP technique

(c) Using the 1st-UIP backjumping strategy, update the list of literals above after the backjumping step and the unit-propagation of the UIP

[SCORING: [0...100], 25 points each for correct answers to (a) and (c), 50 points for correct answer to (b). No penalties for wrong answers..]

(8)

7

Given the following generalized B¨uchi automaton Adef=⟨Q, Σ, δ, I, F T ⟩, {a, b} being labels, with two sets of accepting states F T def={F 1, F 2} s.t. F 1def={s2}, F 2def={s1}:

s1 s2

F2 F1

a a

b b

convert it into an equivalent plain B¨uchi automaton.

[SCORING: [0...100], 100 pts for a correct answer. No penalties for a wrong answer.]

(9)

Consider the following LTL formula:

φ def= (Fr)→ (pUq)

and the following three states of the construction of the tableau Tφ of φ:

S1 : ⟨ q, p, ¬X(pUq), r, XFr⟩

S2 : ⟨¬q, p, X(pUq), r, ¬XFr⟩

S3 : ⟨ q, ¬p, ¬X(pUq), ¬r, ¬XFr⟩

For each of the following statements, say if it is true or false.

(a) S2 is a successor of S1 in Tφ. (b) S3 is a successor of S2 in Tφ. (c) S3 is an initial state of Tφ. (d) S2 is an accepting state of Tφ.

[SCORING [0...100]:

• +25pts for each correct answer

• -25pts for each incorrect answer

• 0pts for each unanswered question ]

[SCORING: [0...100], 25 pts for each correct answer. No penalties for wrong answers.]

(10)

9

Given the following LTL Model Checking problem M |= φ expressed in NuXMV input language:

MODULE main

VAR x : boolean; y : boolean;

INIT (!x & !y)

TRANS (next(x) <-> !x) & (next(y) <-> (x<->y)) LTLSPEC G (x<->y)

1. Write a Boolean formula corresponding to the Bounded Model Checking problem with k = 2.

2. Is there a solution? If yes, find the corresponding execution.

3. From the answers of questions 1) and 2) we can deduce (a) that M |= φ.

(b) that M ̸|= φ.

(c) nothing.

[SCORING: [0...100], 50 pts for question 1, 25pts each for questions 2, 3. No penalties for wrong answers..]

(11)

Consider the following switch e in a timed automaton:

L

1

(y ≤ 5) (y ≥ 4) a y := 0 L

2

and consider the zone Z1def=⟨L1, φ⟩ s.t

φdef= (x≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2).

Compute succ(φ, e), displaying the process in a cartesian graph.

[SCORING: [0...100], 100 pts for a correct answer, -33 pts for a wrong answer, 0pts if unanswered..]

Riferimenti

Documenti correlati

where prefix is defined as the CP dimension ( #define prefix 64 ), OFDMA_symbol_os is the symbol offset of the considered burst (i.e. the OFDMA symbol at which the burst starts: in

(a) List the sequence of unit-propagations following after the last decision, each literal tagged (in square brackets) by its antecedent clause?. (b) Derive the conflict clause

(a) List the sequence of unit-propagations following after the last decision, each literal tagged (in square brackets) by its antecedent clause.. (b) Derive the conflict clause

Since there is only one (relevant) positive U-subformula in φ, we have only one group of accepting states, these which belong to sat( ¬(pUq)) ∪ sat(q).. S 2 does not belong to

The search for an element always requires O(log(N )) steps, N being the number of elements contained in the tree.. The search for an element always requires Θ(N ) steps, N being

If a binary search tree is created from an empty one by inserting one-by-one a sequence of elements in decreasing order, that the resulting tree is balanced.. The search for an

The connection between DEA and FBA is made by assuming that the FBA model describes the metabolic states of the cells in 0: the input and output of each the DMU in the DEA

È notorio come la locuzione “hardship”, descrittiva d’un fenomeno d’importanza crescente nell’ambito della contrattualistica internazionale e tendenzialmente utilizzata