# CS代考程序代写 algorithm 1 0 0 0 0 3

1 0 0 0 0 3

Prof. Dr.-Ing. Jo ̈rg Raisch

Germano Schafaschek

Soraia Moradi

Behrang Nejad

Fachgebiet Regelungssysteme

Fakulta ̈t IV Elektrotechnik und Informatik Technische Universita ̈t Berlin Lehrveranstaltung ”Ereignisdiskrete Systeme“ Wintersemester 2019/2020

Exercise 4 — Solution

Exercise 4.1

The specification can be written as

1 1 0 1 0x(k)≤ 4 .

Γb

One way to test for ideal enforceability is to compute the ideal controller and check if it can be realised

(according to Definition 2.11). The initial marking of the controller places is given by

x0c =b−Γx0 =[3 4]′ , and the controller incidence matrix by

−1 1 0 1 0 Ac=−ΓA= −1 0 1 0 1 ,

where A is the incidence matrix of the plant. The plant with the controller is shown in Figure 1. t2 p2 t3

pc1

t1p1 p3

t4 p4 t5

p5

Figure 1: Plant with controller (Exercise 4.1).

pc2

Since there are no unobservable transitions, it suffices to check if there are any arcs from controller places to uncontrollable transitions. The only uncontrollable transitions are t3 and t5, to which there are clearly no arcs from any of the controller places. Equivalently, we can check if condition (2.23) from the lecture notes holds; namely, if −ΓAouc ≥ 0 (note that here there is no need to check condition (2.24), since there are no unobservable transitions). In this case, −ΓAouc is formed by the third and fifth columns of Ac,

0 0 −ΓAouc = 1 1 ,

1

so clearly −ΓAouc ≥ 0, and (2.23) is verified.

What is left to check is the initial marking, according to condition (2.25). In this case, we have

x0 = [0 0 2 0 1]′, so Γx0 = [0 0]′ ≤ b, and (2.25) also holds. Having computed the ideal supervisor, however, this can actually be directly verified by simply checking x0c, since it is clear that condition (2.25) holds if and only if x0c ≥ 0.

We therefore conclude that the specification is ideally enforceable.

Exercise 4.2

a) ThespecificationcanbewrittenintheformΓx(k) ≤ b,withΓ = [0 0 0 0 1]andb = 1. Applying the standard procedure, one obtains x0c = 1 and Ac = [0 0 0 − 1 1].

b) We check condition (2.23) from the lecture notes (page 33). In this case we have −ΓAouc = −1, so the condition is not fulfilled and the specification is not ideally enforceable.

c) Applying the algorithm for the case of uncontrollable transitions: 1.

2. J = {1}

3. Let ̄j = 1

0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010

1000001 (since J ̸= ∅, proceed to step 3)

a) I = {2, 4}

b) Let ̄i=4;then,d=lcm{1,1}=1 c)

0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010

0000101

4. Gotostep2

2. J = ∅, therefore go to step 6

6. Thealgorithmends,yielding r1T =[0 0 0 1 0] and r2 =1

The new specification is then given by Γ1x(k) ≤ b1, with

Γ1 = [0 0 0 1 0] + Γ = [0 0 0 1 1] and b1 = b = 1 ,

and the new controller can be computed as

Ac1=−Γ1A=[00 −101] and x0c1=b1−Γ1×0=1.

Toobtainasecondspecification,weapplythealgorithmagain,onlynowchoosing ̄i=2 instep 3.b, as follows:

2

1.

2. J = {1}

3. Let ̄j = 1

0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010

1000001 (since J ̸= ∅, proceed to step 3)

a) I = {2, 4}

b) Let ̄i=2;then,d=lcm{1,1}=1 c)

0100000 −1 0 1 0 0 0 0 C=0001000 −1 0 0 0 1 0 0 1000010

0010001

4. Gotostep2

2. J = ∅, therefore go to step 6

6. Thealgorithmends,yielding r1T =[0 1 0 0 0] and r2 =1

The new specification is now given by Γ2x(k) ≤ b2, with

Γ2 = [0 1 0 0 0] + Γ = [0 1 0 0 1] and

and the new controller can be computed as Ac2=−Γ2A=[−1 −1001] and

x2(k) + x3(k) ≤ 3 , x5(k) + x6(k) + x7(k) + x8(k) ≤ 3 , x5(k) + x6(k) ≤ 2 ,

or, in matrix form,

0 1 1 0 0 0 0 0 3 0 0 0 0 1 1 1 1x(k)≤3.

00001100 2

Γb

The incidence matrix of the (ideal) controller can then be computed as

0 −1 0 1 0 0 0 0 0 Ac=−ΓA=0 0 0 0 −1 0 0 0 1.

0 0 0 0 −1 0 1 0 0

b2 = b = 1 ,

x0c2=b2−Γ2×0=0. The boundedness of the resources can be expressed by the following inequalities:

Exercise 4.3

3

Since in this case there are no transitions which are uncontrollable and observable, condition (2.23) from the lecture notes does not apply here. We therefore check condition (2.24). In this case, we have

0 0 0

Ac =−ΓAuouc =0 0 0 ̸=0,

010

so the condition does not hold and the specification is not ideally enforceable. Since the only line that contains a non-zero entry is the third one, we can alter only the third inequality in the specification by applying the algorithm for the case of uncontrollable and unobservable transitions.

1.

000100000000 000010000000 000001000000

−1 0 0 0 0 0 1 0 0 0 0 0 C= −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 001000000010

0 −1 0 0 0 0 0 0 0 0 0 1

2. Does not apply, skip to step 3

3. L = {2} (since L ≠ ∅, proceed to step 4)

4. Letl ̄=2

a) Z = {7}

b) Letz ̄=7;then,d=lcm{1,1}=1 c)

000100000000 000010000000 000001000000

−1 0 0 0 0 0 1 0 0 0 0 0 C= −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 001000000010

0 0 −1 0 0 0 0 0 0 1 0 1

5. Gotostep2

2. Does not apply, skip to step 3

3. L = {3} (since L ≠ ∅, proceed to step 4)

4. Letl ̄=3

a) Z = {8}

b) Letz ̄=8;then,d=lcm{1,1}=1

4

c)

000100000000 000010000000 000001000000

−1 0 0 0 0 0 1 0 0 0 0 0 C= −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 1 0 0 001000000010

000000000111

5. Gotostep2

2. Does not apply, skip to step 3

3. L = ∅, therefore go to step 7

6. Thealgorithmends,returning r1T =[0 0 0 0 0 0 1 1] and r2 =1

The third line of the specification is then changed:

Γ(3) = [0 0 0 0 0 0 1 1] + Γ(3) = [0 0 0 0 1 1 1 1] and

The new controller can then be computed as

b(3) = b(3) = 2 . 3

0 −1 0 1 0 0 0 0 0

Ac=−ΓA=0 0 0 0 −1 0 0 0 1 and x0c=b−Γx =3.

0

0 0 0 0 −1 0 0 0 1 2

5