Behavioural Models

From Modelling Finite Automata to Analysing Business Processes

Exercises

3.2 Automata with Output

a) Mathematical expression of an automaton

Design an automaton for an office coffee machine whose output is expressed by the following sets and relations:

S = {card insertion, pin insertion, coffee selection, size selection}
Σ = {card_ok, card_not_ok, pin_ok, pin_not_ok, select_Espresso, select_Cappuccino, select_coffee, select_small_cup, select_big_cup}
Λ = {Wrong card, Wrong PIN, Espresso, Cappuccino, small coffee, big coffee, card}
δ = {
        (card insertion, card_not_ok) ↦ card insertion,
        (card insertion, card_ok) ↦ pin insertion,
        (pin insertion, pin_not_ok) ↦ pin insertion,
        (pin insertion, pin_ok) ↦ coffee selection,
        (coffee selection, select_Espresso) ↦ card insertion,
        (coffee selection, select_Cappuccino) ↦ card insertion,
        (coffee selection, select_coffee) ↦ size selection,
        (size selection, select_small_cup) ↦ card insertion,
        (size selection, select_big_cup) ↦ card insertion
}
λ = {
        (card insertion, card_not_ok) ↦ {card, Wrong card},
        (card insertion, card_ok) ↦ {},
        (pin insertion, pin_not_ok) ↦ {Wrong PIN},
        (pin insertion, pin_ok) ↦ {},
        (coffee selection, select_Espresso) ↦ {card, Espresso},
        (coffee selection, select_Cappuccino) ↦ {card, Cappuccino},
        (coffee selection, select_coffee) ↦ {},
        (size selection, select_small_cup) ↦ {card, small coffee},
        (size selection, select_big_cup) ↦ {card, big coffee}
}
s0 = card insertion
F = {}

b) Mealy to Moore transformation

Transform the coffee machine automaton of exercise 3.2a) into an automaton with Moore output.

c) String identifier

Given is the description of an automaton that identifies strings. Follow the tasks below to model it by using automata with output.

An automaton is used for detecting the sequence "10010" in a stream of "1" and "0". The automaton reads the stream and outputs "1", if the sequence "10010" was read (i.e. upon reading "0", if it was preceded by "1001"). Otherwise, the output for each input is "0". If there are overlapping sequences, the automaton only identifies the first word. The automaton terminates without output, if "EOL" is read.

Example:
Data stream: 1100100101001011001010000011EOL
Output:         0000010000000100000100000000

  1. Write down the input and the output alphabet.
  2. Model the automaton as a Mealy automaton.
  3. Model the automaton as a Moore automaton. (Hint: The initial state should not have any output.)
  4. Identify differences and imagine use cases where you would prefer either a Mealy or a Moore automaton.