a, b - IAW - RWTH Aachen University

© Chair and Institute of Industrial Engineering and Ergonomics, RWTH Aachen University

Simulation of Discrete Event Systems

Univ.-Prof. Dr.-Ing. Dipl.-Wirt.-Ing. Christopher M. Schlick

Lehrstuhl und Institut für Arbeitswissenschaft

RWTH Aachen

Bergdriesch 27

52062 Aachen

Tel.: 0241/80 99 440

E-Mail: [email protected]

Unit 2

Languages and Automata

Fall Winter 2013/2014

2- 2 © Chair and Institute of Industrial Engineering and Ergonomics, RWTH Aachen University

1. Languages

- Introduction and Definition

- Operations on Languages

2. Automata

- Introduction and Definition

- Languages generated by Automata

- Blocking

- Unary Operations on Automata

- Binary Operations on Automata

- Moore Automata

- Mealy Automata

- Finite State Machines

Contents


model

dynamic static

time-invariant time-varying

nonlinear linear

discrete states continuous states

event-driven time-driven

stochastic deterministic

continuous-time discrete-time

Focus of lecture and exercise

Focus of lecture and exercise


1. Languages

1. Languages


Basic entity of the formalism of discrete event systems is the symbol. A symbol is an abstract

entity which will not be defined formally because of its intuitive meaning. Alphabetic characters

and decimal numbers of the English language are examples of frequently used symbols of this

lecture series. However, also the mathematical formulas represent a symbol system of its own

right with a higher cardinality.

An alphabet is a finite set of symbols. If the symbols of an alphabet are concatenated according to

well defined rules, strings are generated. These strings may be stored sequentially in a

computer file. The -symbol represents a string without symbols (empty string). The empty string

symbol is the neutral element of the concatenation operation. The rules for string generation can

be considered as a formal automata-theoretic language.

In the domain of discrete event systems symbols encode both events and states. However, only

events are concatenated on the basis of formal languages. The generated events strings can be

considered as a symbolic representation of the behavior of a discrete event system. In that

sense formal languages are some kind of “rule base” that explains valid behavior of a discrete

event system.

Introduction to languages


1. Def.: A (formal) language L with regard to an event set E is the set of all strings, which can be

generated using the elements of the set following another set of well defined

concatenation rules.

Examples for E={a, b, c}:

L1={a, b, ab, ba}

2. Def.: A string s (synonym word) is a sequence of events. The length of the string is denoted

with |s| and represents the number of concatenated events. The empty string is denoted

by the symbol and has zero length.

3. Def.: The Kleene closure E* is the set of all strings, which can be concatenated using the

elements of the event set E including with an arbitrary set of well defined concatenation

rules; therefore, a language L is always a subset of the Kleene closure E*.

L2={all strings being equal when read forwards and backwards} = {, a, b, aba, bab, aca, cac,...}

E*={, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, ...}

|E*|=

L3={anbn: 0 <= n <= 2} = {, ab, aabb}

Definitions


4. Def.: Concatenation of languages: If La, Lb E*, then

5. Def.: Operations on strings: If s = tuv with t, u, v E*, then

- t is a prefix string of s

- u is a substring of s

- v is a suffix string of s

6. Def.: Prefix closure: Let L E*, then

* *: : ( )L s E t E st L

*: : ( ) ( ) ( )a b a b a a b bL L s E s s s s L s L

The prefix closure of a language L therefore includes the prefix strings of all strings of L; in

general L is a subset of its prefix closure; if the prefix closure and L are equal, the language

is a prefix closed language.

Operations on languages

Note that and s are prefixes (respectively substrings, suffixes) of s.


2. Automata

2. Automata


7. Def.: A deterministic automaton G is represented by the tuple

G = (X, E, f, , x0, Xm) where

- X is the finite set of the states of the automaton,

- E is the finite set of transition enabling events,

- f : X E X is the state transition function,

- : X 2E the active event function (or feasible event function),

- x0 denotes the initial state of the automaton, and

- Xm X is the set of marked states.

Notation of transition function f: f(x, e) = y means, that a transition from state x to state y is caused

by the event e; usually, f is an incomplete mapping.

Notation of active event function : (x) represents simply the set of all events e, where the

transition function f(x, e) = y is defined; (x) can be considered as the set of active events of G

being in state x. 2E is a shorthand notation for the power set of E.

Definition of automaton

The marked states Xm are an especially important part of the formal specification of an

automaton. The meaning of a marked state is an allowed end state of the system. In that sense it

represents a significant sub-goal that has to be reached by design.


- State set: X = {0, 1}

- Event set: E = {a, b}

- Transition funct.: f(0, a) = 1; f(0, b) = 0; f(1, a) = 1; f(1, b) = 0

f is a complete mapping

- Active event funct.: (0) = {a, b}; (1) = {a, b}

- Initial state: x0 = 0

- Marked states Xm = {1}

State transition

diagram:

0

a

a

b

b

Denotes initial

state

Marked

„1“-state

1

Transition

Events

Example of automaton

States


8. Def.: A language L is generated by G = (X, E, f, , x0, Xm), if

L(G) := {s E* : f(x0, s) is defined}

9. Def.: A language Lm is marked by G = (X, E, f, , x0, Xm), if

Lm(G) := {s L(G) : f(x0, s) Xm}

In other words, when generating the strings of the language there must be a path that starts by the

initial state and follows the directed arcs of the state transition diagram of the corresponding

automaton.

In other words, when generating the strings of the marked language there must be a path that starts

by the initial state, follows the directed arcs of the state transition diagram of the corresponding

automaton and ends in a marked state.

1. Proposition: The automata G1 and G2 are equivalent, if

L(G1) = L(G2) Lm(G1) = Lm(G2)

They must simply generate and mark the same language.

Relation between languages and automata

0 0 0 1 2 0 1 2( , ) ( ( ( , ), ), ...)f x s f f f x s s s with s s s s

0 0 0 1 2 0 1 2( , ) ( ( ( , ), ), ...)f x s f f f x s s s with s s s s


Lm(G1) = {a, aa, aba, aaa, ...}

strings must end with a

L(G1) = {a, aa, ab, aba, abab, ...}

Lm(G2) = {a, aa, aaa, aba, aaaa, ...}

L(G2) = {a, aa, ab, aba, abab, ...}

L(G1) = L(G2) Lm(G1) = Lm(G2) => G1 and G2 are equivalent

0

a

a

b 1

0

a

b 1

a

2 a

b

Example of relation between languages and automata


2. Proposition: An automaton is blocked, if

( ) ( )mL G L G

3. Proposition: An automaton is non-blocking, if

( ) ( )mL G L G

Types of blocking

Deadlock:

There is a deadlock in an automaton, if

the active event function of a reached

state is equal the empty set and a

marked state as a possible end state has

not been reached.

Livelock:

There is a livelock in an automaton, if

continuing state transitions only cover

unmarked states and there is no transition

to “break out” of this subspace. In that

sense the automaton iterates in an infinite

loop.

Analysis of automata: blocking


1.blocking condition: ( ), but ( )maba L G aba L G

0 a

b

b

1

b

2 b

4

3 a

5

a

6

a

c c c

b

2.blocking condition: ( ), but ( )mabc L G abc L G

Deadlock

Livelock

Blocking example


10. Def.: The accessible part of an automaton G is represented by the „Ac“-operator being

defined as:

Ac(G) := (Xac, E, fac, , x0, Xm,ac) with

- Xac= { x X: s E* with f(x0 , s) = x }

- Xm,ac= Xm Xac

- fac = f | Xac E → Xac (the transition function is restricted to the smaller domain of

accessible states Xac )

In other words, the application of the Ac-operator results in removing all states and transitions of

the automaton, which cannot be accessed when following the directed arcs of the state

transition diagram starting with the initial state.

Clearly, this operator does not modify the generated and marked language of an original

automaton G.

Operations on automata: unary (I)


11. Def.: The co-accessible part of an automaton G is represented by the „CoAc“-operator, which

is defined as:

CoAc(G) := (Xcoac, E, fcoac, , x0,coac , Xm) with

- Xcoac= { x X: s E* with f(x , s) Xm }

- x0,coac =

- fcoac = f | Xcoac E → Xcoac (the transition function is restricted to the smaller domain of

co-accessible states Xcoac )

In other words, the application of the CoAc-operator results in removing all states and transitions of

the automaton, which do not end in a marked state when following the directed arcs of the state

transition diagram. Therefore, the language being generated by CoAc(G) may have fewer

elements due to state pruning. However, the marked language is not modified when using this

operator.

Clearly, there is a strong logical connection between accessibility, co-accessibility and blocking,

because a blocked automaton requires accessible states, which are not co-accessible !!!

Operations on automata: unary (II)

x0 , if x0 Xcoac

else not defined


13. Def.: The complement of an automaton G is represented by the „Comp“-operator, which is

defined as:

Gcomp(G) := (Xcoac {xd}, E, ftotal, , x0, (Xcoac {xd}) \ Xm ) with

- ftotal(x, e) =

- ftotal(xd, e) = xd for all e E

12. Def.: The „Trim“-operator refers to the accessible and co-accessible part of an

automaton G as

Trim := CoAc(Ac(G)) = Ac(CoAc(G)) .

If the complement operator is applied to an automaton G, the marked language of Gcomp is equal

the complement set of the language being marked by G with respect to the Kleene closure E*.

Operations on automata: unary (III)

f(x, e), if e (x)

xd otherwise (dead state)


Original automaton G

CoAc(G) Trim(G) Complement of Trim(G)

Examples of unary operations on automata


14. Def.: The product of two automata G1 and G2 is defined such as:

G1 G2 := Ac(X1 X2, E1 E2, f, 1 2, (x01, x02), Xm1 Xm2 ) with

- f( (x1 ,x2), e) = ( f1 (x1, e), f2 (x2, e) ), if e 1 (x 1) 2(x 2)

otherwise not defined

In other words, the application of the product operator leads to a synchronization of the

transitions of the automata based on the shared events E1 E2 . All other events give not

defined results and do not result in a reaction of the product automaton. Therefore, the

behavior can be considered as a complete synchronization.

The state of the product automaton is denoted as an ordered pairs (x1, x2). The first component

of the pair is associated with the state of G1 and the second component is associated with the

state of G2.

Operations on automata: binary (I)


0 a

b

a

1

2

a, c c

b

0

a

a

b

b

1

(0,0)

a

a

(0,1)

=

Example of product


4. Proposition: The intersection of two languages can be generated and marked with the help of

the product of the associated automata:

- L(G1) L(G2) = L(G1 G2)

- Lm (G1) Lm (G2) = Lm (G1 G2)

Intersections


15. Def.: The parallel composition of two automata G1 und G2 is defined such as:

G1 || G2 := Ac(X1 X2, E1 E2, f, 1 || 2, (x01, x02), Xm1 Xm2 ) with

- f( (x1 ,x2), e) = ( f1(x1, e), f2(x2, e) ), if e 1 (x 1) 2(x 2)

( f1(x1, e), x2 ), if e 1 (x 1) \ E 2

( x1, f2(x2, e) ), if e 2 (x 2) \ E 1

otherwise not defined

In other words, the application of the parallel composition operator usually leads to a partial

synchronization of the transitions. A complete synchronization of transitions in the parallel

composed automaton occurs only, if the intersection of the active events sets is involved. In

other cases the singular automata are processing the events in parallel and therefore can be

regarded as concurrent processes.

In the automata theory the technical term concurrent automata applies, which are synchronized

according to the events e 1 (x 1) 2(x 2).

Operations on automata: binary (II)


0 a

b

a

1

2

a, c c

b

0

a

a

b

b

1

(0,0) c

b

(2,0)

||

= (0,1)

c (2,1)

c

b

(1,0)

a, c (1,1) a

a b b a

a

a

Example of parallel composition


16. Def.: A Moore automaton GMoore is represented by the tuple

GMoore = (X, E, f, , x0, Xm, Eoutput, foutput) where

- X is set of states of the automaton,

- E is the event set,

- f : X E X is the state transition function,

- : X 2E is the active event function,

- x0 represents the initial state,

- Xm X is the set of marked states,

- Eoutput is the set of output events, which are bound to the states, and

- foutput : X E Eoutput denotes the output function.

1

Example of Moore automaton: binary water valve

Eoutput = {NO_FLUX, FLUX}

foutput (0, open_valve) = FLUX

foutput(1, close_valve) = NO_FLUX

(foutput is incomplete mapping)

0

open_valve

1 close_valve

NO_FLUX FLUX

Automata with input and output: Moore automaton


Eoutput = {generate_alert, reset_alert}

f(0, critical_pressure / generate_alert) = 1

f(1, noncritical_pressure / reset_alert) = 0

17. Def.: A Mealy automation GMealy is represented by the tuple

GMealy = (X, E, f, , x0, Xm, Eoutput), where

- X is the set of states of the automaton,

- E is the event set,

- Eoutput is the set of output events being bound to the transitions,

- f : X (E Eoutput) X is the state transition function,

- : X 2E is the active event function,

- x0 represents the initial state, and

- Xm X is the set of marked states.

Example of Mealy automaton: binary safety valve

0

critical_pressure / generate_alert

1

noncritical_pressure / reset_alert

Automata with input and output: Mealy automaton


5. Proposition: The Moore automaton GMoore and the Mealy automaton GMealy can be transformed

to an automaton G without outputs.

-L(GMoore) E*: L(G) E* with L(GMoore) = L(G)

-L(GMealy) E*: L(G) E* with L(GMealy) = L(G)

Transformation procedure for Mealy automaton:

Define all combinations of input / output events as singular events of the transformed event set

and specify the state transition function accordingly.

Transformation procedure for Moore automaton:

Associate the state output to all events that enter the state and thus construct a Mealy

automaton. Then, transform the Mealy automaton according to the above procedure.

In other words, the Moore and Mealy notation are equivalent approaches to modeling and

simulation of discrete event systems. Individual preference may depend on the application

domain.

Transformation of automata


6. Proposition: Each language L can be marked by an automaton G:

-L E*: G with L = Lm(G)

Synthesis example for G: L= {, ab, aabb, aaabbb, ...} = {anbn: n >= 0}

0 1 a

2 a

3 a . . .

4

b

5

b

6

b

7

b

8

b

. . .

. . .

. . .

Synthesis of automata based on languages


7. Proposition: There are languages, which cannot be marked by an automaton with a finite

number of states:

-L E*: G with L = Lm(G) and |X|

18. Def: A language is regular, if it can be marked with the help of an automaton with a finite

number of states. Otherwise the language is irregular.

The associated technical term is “finite-state automaton” marking a regular language.

Finite-state automata are an important subset of the set of all automata, because they can be

simulated efficiently with the help of digital computers. If irregular languages have to be

simulated with automata-theoretic methods, theoretically a computer with an infinite amount of

storage is needed that costs an infinite amount of money (at least today!).

In the next but one lecture we are going to introduce marked Petri nets, which are an ingenious

modeling method that is able to generate and mark also irregular languages with a finite

structure of states and transitions. Therefore, we have to introduce a new modeling element

that is able to represent local event processing.

Example : L = {, ab, aabb, aaabbb, ...} = {anbn: n >= 0}

Regular and irregular languages


• CASSANDRAS, C.,G.; LAFORTUNE, S. (2007): Introduction to Discrete Event Systems.

2nd edition. Boston (MA): Kluwer Academic Publishers.

• HOPCROFT, J.E.; MOTWANI. R.; ULLMAN, J.D. (2001): Introduction to Automata

Theory, Languages and Computation. Second edition. Boston (MA): Addison-Wesley.

References


Open Questions ???

Questions ?

Documents

a, b - IAW - RWTH Aachen University