Week 6

Question 1

What is a labelled transition system?

Answer 1

A formal representation of the states, the stepwise behaviour, and the initial states of a system.

A tuple (S, s0, Act, ->) where:
- S is the set of states
- s0 is the intial state
- Act is a set of actions
- -> subset of (S * (Act U {pi}) * S) is a transition relation

where pi is an internal action

Question 2

What is an internal action

Answer 2

An internal action is an ordinary action which we cannot directly observe

Question 3

What are the predecessors of a state s

Answer 3

The predecessors of a state s’ are all of the states such that there exists an action for which the LTS transitions from s’ to s.

Question 4

What are the successors of a state s

Answer 4

All states s’ for which there exists an action for which the LTS transitions from s to s’.

Question 5

The traces of a given state s are

Answer 5

all of those combinations of actions (including internal actions) that can start in state s and take the LTS to some other state

represented by a line with two arrows

Question 6

The traces of a given LTS

Answer 6

are the traces of the initial state of that LTS

Question 7

Weak traces

Answer 7

consider internal transitions silent or unobservable

still consider them, but the internal transitions are just not mentioned in the traces

represented by an implication sign

Question 8

s after y meaning

Answer 8

the set of states that can be reached by s after following the weak trace y

since this is a weak trace, internal transitions are allowed at any point

Question 9

S’ after y (where S’ is a set of states)

Answer 9

the set of states reached after following trace y from any of the sets in S’

Question 10

Reach(s) meaning

Answer 10

the set of states for which there exists a trace such that they can be reached from s by following that trace

Question 11

The reachable states of an LTS are

Answer 11

all of the states reachable from the LTS’ initial state

Question 12

When is an LTS without internal transitions deterministic?

Answer 12

When for all combinations of three states and one action, if one state can follow that same action to two of the states, then those states are the same state.

Question 13

When is an LTS with internal transitions determinstic?

Answer 13

Never, LTS’s with internal transitions are alwasys considered non-deterministic

Question 14

Parallel Composition of LTS’s

Answer 14

First, one needs a set of handshaking actions H, which are a subset of the intersection of the sets of actions of the two LTS’s

Then, the parallel composition LTS is as follows:

S: S1 * S2
s0 = (s10, s20)
Act = Act1 U Act2

and -> is as follows

For all actions in H:

(s1,t1)->a(s2,t2) only if s1 goes to s2 with a in LTS 1 and t1 goes t2 in LTS2.

For all actions not in H:
(s1,t1)->a(s2,t1) if s1->as2 in LTS1
(s1,t1)->a(s1,t2) if t1->t2 in LTS2

Question 15

Three Types of States in State Machine Diagrams

Answer 15

1. Basic states:
   - simple state, no nested states inside
2. Composite state / Or:
   - at most one nested state inside is current
3. Orthogonal / And:
   - each region is current, and is itself considered an or-state

Question 16

What are the children of a basic state?

Answer 16

it has no children

Question 17

What are the children of an or state?

Answer 17

The states contained directly inside

Question 18

What are the children of an and state?

Answer 18

All of the different regions inside at depth 1

Question 19

What are the descendants of a state s

Answer 19

The state s, its children and all of the descendants of its children

Question 20

What are the ancestors of s?

Answer 20

All of the states for which s is a descendant

Question 21

What are strict descendants/ascendants?

Answer 21

The descendants/ascendants excluding the state itself

Question 22

The state configuration with respect to a state s is:

Answer 22

a subset of the descendants of s such that:

s is in the configuration
for every or-state in the configuration, exactly one child of it is in the configuration
for every and state in the configuration, all children of it are in the configuration

Question 23

What is a transition, formally, in a state machine diagram?

Answer 23

A transition is a tuple (ss, Et, C, Eg, st) where:

ss is the source state
Et are the trigger event(s)
C are the guards
Eg are the generated events
st is the target state

Question 24

Least common strict or-ancestor (LCSOA)

Answer 24

the or-state having all the states in the set as descendants, while being closest in hierarchy distance to these states

if there is no such or-state, it is said that the lcsoa is “root”

Question 25

What is the scope of a given transition?

Answer 25

The lcsoa of the source and target state

Question 26

The unique exit state of a transition

Answer 26

The state that is both:
1. the child of the scope of transition
2. the ancestor of the source of the transition

captures the part of the configuration left when executing the transition

Question 27

The exit set of a transition

Answer 27

The unique exit state plus all its descendants in the current configuration

Question 28

The unique enter state of a transition

Answer 28

The state satisfying both the conditions:
1. the child of the scope of transition
2. ancestor of the target of the transition

captures the (sub)configuration entered when executing the transition

Question 29

The enter set of a transition

Answer 29

the target state and all descendant of the unique enter set that are not ancestors of the target state

Question 30

Situation

Answer 30

a pair st = (conf, Ev) where:
- conf is a configuration
- Ev are the available events

Question 31

When is a transition tr with dispatched event f and situation (conf,Ev) enabled?

Answer 31

It is enabled if and only if:
1. its source state is in the configuration
2. the dispatched event is a trigger of the transition
3. the guard is satisfied

Question 32

When is a transition tr with dispatched event e at situation st=(conf,Ev) fireable>

Answer 32

When:
1. The transition is enabled for that event and situation.
2. For all other enabled transitions for that event and situation, their source state is not a strict descendant of the source state of this transition’s source state.

Question 33

When are two transitions conflicting in a configuration?

Answer 33

Two transitions are conflicting in a configuration if and only if their exit sets overlap.