Exercise 1 We consider words over the alphabet {a, b} as transition systems ‫܂‬S, Es, Er, Pa, Pb‫܂‬
where the states S are the positions, the two predicates Pa and Pb label each position with the corresponding
letter, and the two edge relations are
Es = {‫܂‬i, i + ‫܂‬ i < n − } ,
Er = {‫܂‬i, k‫܂‬ i ≤ k < n } .
(where n = S is the length of the word). Define the following languages in modal logic.
(a) All words starting with the letter a.
(b) All words consisting only of letters a.
(c) All words ending with the letter a.
(d) a∗
b∗
(e) All words containing the factor bb.
(f) All words containing at least two letters b.
(g) All words containing exactly two letters b.
(h) (ab)∗
Exercise 2 Translate the following formulae into first-order logic.
(a) [a]P → P
(b) P → ‫܂‬a‫܂‬Q
(c) [a](P ∧ ‫܂‬b‫܂‬Q) → (‫܂‬a‫܂‬P ∨ ‫܂‬b‫܂‬Q)
Exercise 3 Prove the following modal formulae using tableaux.
(a) Ԃ(P ↔ (Q ∧ R)) → (ԂP ↔ (ԂQ ∧ ԂR))
(b) ¬ Ԃ ԂP → ¬P
(c) Ԃ(P ∧ ¬P) → ԂQ
(d) ¬ P → Ԃ(P → Q)
Exercise 4 Find CTL*-formulae defining the following properties of {a, b}-labelled trees.
(a) There is at least one label b.
(b) Every path contains some b.
(c) Every path contains at least two b.
(d) All paths contain infinitely many b.
(e) Some path contains infinitely many b.

Exercise 5 We model an elevator in a building with  stories.
(a) Describe the elevator as a transition system.
(b) Write a specification for the elevator in modal logic and in LTL. Start with the following two
statements, then add your own.
(i) The elevator never moves when the door is open.
(ii) If the button on floor  is pressed, the elevator will eventually stop at that floor and open
the door.
Check that your system from (a) satisfies these formulae.
