24
Các thuật toán biến đổi các quá trình tuần tự thành các quá trình tơng
tranh đợc trình bày trong luận án là khá chi tiết, đánh giá đợc độ phức tạp
tính toán và dễ dàng cài đặt trên máy tính.
3) Tính toán cận trên độ phức tạp otomat đoán nhận ngôn ngữ sinh bởi
nguồn, biểu thức chính quy, sơ đồ sinh và chùm đầu.
Những kết quả đạt đợc của luận án có thể phát triển cho các mô hình
biểu diễn khác của hệ thống nh: hệ mạng theo thời gian, hệ thống công
nghệ thông minh, otomat vào - ra, otomat sác xuất và có thể áp dụng vào
thực tế nh: điều khiển tối u các dây chuyền sản xuất công nghiệp, điều
khiển các giao tác trong tìm kiếm và khai phá dữ liệu trong các cơ sở dữ liệu
lớn
Đó cũng là những ý tởng mà tác giả dự định nghiên cứu trong thời
gian sắp tới.

nguồn, biểu thức chính quy, sơ đồ sinh, chùm đầu Do vậy, việc nghiên
cứu, khảo sát, tính toán độ phức tạp otomat của một số lớp ngôn ngữ đợc
sinh ra từ các công cụ trên vẫn là một đề tài đang đợc nhiều ngời quan
tâm. M. Linna đã xác định độ phức tạp otomat cho các thuật toán đoán nhận
các -ngôn ngữ phi ngữ cảnh. Đô phức tạp otomat của một số ngôn ngữ
cũng đợc nghiên cứu bởi Đặng Huy Ruận, Đỗ Long Vân và Phan Trung
Huy ở Việt Nam, việc nghiên cứu điều khiển hệ thống tơng tranh và độ
phức tạp của ngôn ngữ hình thức đợc tập trung nghiên cứu tại Viện Toán
học và Trờng Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội.
Mục tiêu của luận án là sử dụng đồ thị định h
ớng gán nhãn để xây
dựng một số thuật toán điều khiển tơng tranh các quá trình xảy ra trên các 2
hệ mạng điều kiện - biến cố và trên các hệ mạng vị trí - chuyển. Tác giả
cũng sử dụng đồ thị để biểu diễn một số công cụ sinh ra ngôn ngữ nh:
nguồn, biểu thức chính quy, đồ thị sinh, sơ đồ sinh và chùm đầu và
nghiên cứu đánh giá cận trên độ phức tạp otomat của các công cụ này.
Những kết quả đạt đợc trên các ngôn ngữ sinh bởi các công cụ này rất có ý
nghĩa.
Trong bản luận án này chúng tôi đã đóng góp đợc những kết quả
chính sau đây:
1) Mô tả bài toán điều khiển tơng tranh các quá trình trên một hệ
thống.
2) Xây dựng đồ thị các trờng hợp và ứng dụng nó để xây dựng
thuật toán điều khiển tơng tranh các quá trình trên hệ mạng
điều kiện - biến cố.
3) Cải tiến thuật toán xây dựng đồ thị phủ của một hệ mạng vị trí -
chuyển và ứng dụng nó để xây dựng thuật toán điều khiển tơng

, x
j+1
, , x
k-1
, x
k
> sao cho, mỗi đỉnh trong dãy (không kể đỉnh
đầu tiên) kề với đỉnh trớc nó bằng một cạnh nào đó, nghĩa là: i = 2, 3,
, k-1, k : (x
i-1
,x
i
) E.
Chu trình là một đờng đi khép kín.
1.1.3. Một số cách biểu diễn đồ thị trong máy tính 23
đỉnh trong tập q nhờ các cung cốt yếu có nhãn là {a}. Đặt f(q,a) =
g(T
Ii
(q,a)).
- Trạng thái kết thúc: trạng thái q q
0
đợc xem là trạng thái kết thúc
của otomat A
i
nếu tồn tại ít nhất một từ p sao cho p

L(I

ID
+
.

Phần KếT luận
Bằng cách sử dụng các công cụ của lý thuyết đồ thị chúng tôi đã
xây dựng đợc hai thuật toán điều khiển tơng tranh các quá trình xảy ra
trên các hệ thống phân tán. Đồng thời, kết hợp giữa lý thuyết đồ thị với các
phơng pháp truyền thống của otomat, chúng tôi đã xây dựng đợc các
otomat hữu hạn đoán nhận một số lớp ngôn ngữ và đánh giá cận trên độ
phức tạp otomat cho các ngôn ngữ này. Trong luận án này, chúng tôi đã đạt
đợc đợc các kết quả chính sau đây:
1) Bản luận án đã phát biểu bài toán điều khiển tơng tranh các quá
trình xảy ra trên một hệ thống và xây dựng đợc thuật toán đầy đủ hoá đồ
thị các trờng hợp của một hệ mạng điều kiện - biến cố. Thuật toán cho
chúng ta đồ thị các trờng hợp đầy đủ của hệ mạng tơng ứng. Khi đó, dãy
các nhãn trên mỗi đờng đi của đồ thị các trờng hợp đầy đủ sẽ chỉ ra một
quá trình tơng tranh xảy ra trên hệ mạng này.
2) Đồng thời luận án cũng đã xây dựng thuật toán tìm các bớc tơng
tranh cực đại trên một hệ mạng vị trí - chuyển nhờ đồ thị phủ của nó. Kết
quả của thuật toán này chỉ ra một chiến lợc điều khiển tối u trên các hệ
thống đợc biểu diễn bởi hệ mạng vị trí - chuyển. 22
Giả sử I
i
là một chùm đầu. Khi đó với từ p tuỳ ý và mọi chữ cái a thuộc
ta xác định các tập hợp sau đây:



3
(pa) = { t , 1 t s mà pa N
Ii
(e
jt
) và L
Ii
(K(e
jt
),)}.
Bổ đề 3.12: Với mọi từ p và mọi chữ cái a thì:
Z
Ii
(pa) =
1
(pa)
2
(pa)
3
(pa).
Hệ quả 3.13: Với mọi sơ đồ sinh đơn giản S, mọi từ p và mọi chữ cái a
ta đều có: Z
S
(pa) =
1
(pa).
Hệ quả 3.14: Giả sử S là sơ đồ sinh đơn giản, p
1
, p

p
2
là các từ tuỳ ý và a là chữ cái thuộc .
Nếu g
i
(p
1
) g
i
(p
2
) thì g
i
(p
1
a) g
i
(p
2
a).
Hệ quả 3.16: Nếu g
i
(p
1
a) g
i
(p
2
a) thì với mọi từ q ta đều có: g
i

i

nh sau:
- Tập trạng thái Q(A
i
) = {s
0
(I
i
)} {g
i
(p) p }.
- Trạng thái khởi đầu của A
i
là q
0
= {s
0
(I
i
)}.
- Hàm chuyển trạng thái f xác định nh sau: với chữ cái a ,
1) f (q
0
, a) = g
i
(a).
2) Giả sử q Q(A
i
) , q q

Đầu vào: Đồ thị G = (V,E) và ha đỉnh a, b thuộc V.
Đầu ra: Câu trả lời: có / không.
1) Xây dựng ma trận kề A cho đồ thị G.
2) Tính ma trận tổng các luỹ thừa T = A
1
+ A
2
+ + A
n-1
.

3) Nếu T[a,b] 1 thì kết luận là có đờng đi từ đỉnh a đến đỉnh b,
ngợc lại thì kết luận là không có.
Hiển nhiên, thuật toán trên có độ phức tạp là O(n
4
).
1.1.5. Đồ thị gán nhn

Giả sử G = (V, E) là một đồ thị và L là một tập hợp không rỗng nào
đó. Hàm n : E L đợc gọi là hàm gán nhãn trên các cạnh của đồ thị đã
cho. Khi đó, mỗi cạnh e E sẽ đợc gán nhãn n(e) L.
1.1.6. Các thuật toán duyệt đồ thị
Phép duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị này
thành một danh sách tuyến tính.
1) Duyệt đồ thị theo chiều sâu
Sử dụng stack S để lu trữ các đỉnh đang duyệt và danh sách L
chứa kết quả.
Thuật toán 1.4 (Duyệt đồ thị theo chiều sâu)
Dữ liệu: Mảng các danh sách kề DK của đồ thị G.
Kết quả: Danh sách L tất cả các đỉnh của đồ thị G.

2) Duyệt đồ thị theo chiều rộng
Sử dụng hàng đợi Q để lu trữ các đỉnh đang đợc duyệt và và
danh sách L chứa kết quả.
Thuật toán 1.5 (Duyệt đồ thị theo chiều rộng)
Dữ liệu: Mảng các danh sách kề DK của đồ thị G.
Kết quả: Danh sách L tất cả các đỉnh của đồ thị G.
1 procedure D_RONG (v) ;
2 begin
3 Q := ;
4 enqueue v into Q ; {nạp v vào cuối hàng đợi Q}
5 Duyet [v] := true ;
6 while Q do
7 begin
8 dequeue x from Q ; {loại x ra khỏi đầu Q}
9 Thăm_đỉnh (x) ;
10 L := L . x ;
11 for u DK[x] do
12 if NOT Duyet [
u] then
13 begin
14 enqueue u into Q ;
15 Duyet [u] := true ;
16 end ;
17 end ;
18 end ; 21
Định lý 3.9: Với mọi sơ đồ sinh S, cận trên độ phức tạp otomat của nó là
()1

đồ thị sinh trong sơ đồ sinh S mà I phụ thuộc.
3.4.2. Otomat hữu hạn đơn định đoán nhận ngôn ngữ sinh bởi chùm đầu
Để xây dựng otomat hữu hạn đơn định có ít trạng thái nhất đoán nhận
đợc ngôn ngữ sinh bởi chùm đầu ta tiến hành ba bớc sau đây.
Bớc 1: Nghiên cứu cấu trúc các trạng thái của otomat
Định nghĩa hàm g
i
:
+

)(
2
i
ID
+
một cách đệ quy nh sau:
Với từ p , giả sử e
j1
, e
j2
, , e
js
là tất cả các cung bù trong chùm đầu
I
i
và với mỗi chùm đầu I
jt
(1 t s) thì hàm g
jt
(p) đã đợc xác định. Thế thì:

1
) g
i
(p
2
) và p
1
L(I
i
) thì p
2
L(I
i
).
Hệ quả 3.11: Nếu g
i
(p
1
) g
i
(p
2
) và p
2
C(L(I
i
)) thì p
1
C(L(I
i

t
t
SL
1
)(
=
và |D(S)|

|)D(S|
1
t

=
k
t
.
Bổ đề 3.4: Với mọi sơ đồ sinh đơn giản S đều có thể xây dựng đợc sơ đồ
sinh đơn giản S' sao cho: |D(S')| |D(S)| và L(S') = {X
*
Y L(S) , |X |
= | Y|}.
Bổ đề 3.5: Với mọi sơ đồ sinh S chỉ chứa cung lấy tiền tố, ta đều có thể xây
dựng đợc sơ đồ sinh đơn giản S', sao cho |D(S')| < |D(S)|
3
và L(S') = {X X
là tiền tố của từ thuộc đồ thị sinh I
i
thuộc S}.
Bổ đề 3.6: Với mọi sơ đồ sinh S chỉ chứa cung lấy hậu tố ta đều có thể xây
dựng đợc sơ đồ sinh đơn giản S' mà |D(S')| < |D(S)|

eee
I
, ,,
, ,,
21
21
][

là kết quả của phép thay thế các cung e
i
bằng
các đồ thị sinh
i
. Thế thì, L(I
1
) = L(I) và |D(I
1
)| |D(I )| +
|)(|
1

=

k
i
i
D
.
Bổ đề 3.8: Với mọi sơ đồ sinh S không chứa cung bù luôn có thể xây dựng
đợc sơ đồ sinh đơn giản S' sao cho: L(S') = L(S) và |D(S')|

2) Hợp của hai ngôn ngữ
3) Giao của hai ngôn ngữ
4) Hiệu của hai ngôn ngữ
5) Phần bù của ngôn ngữ
6) Lặp của ngôn ngữ
7) Lặp cắt của ngôn ngữ
1.2.3. Một số công cụ sinh ngôn ngữ chính quy và mối quan hệ giữa
chúng
a) Văn phạm chính quy
Định nghĩa 1.6: Văn phạm là bộ bốn G = (, V, P, S), trong đó:
- là bảng chữ cái chính,
- V là bảng chữ cái phụ,
- S là một chữ cái phụ và đợc gọi là ký hiệu khởi đầu,
- P là tập hữu hạn các quy tắc dẫn xuất có dạng , với ,
(
V)
*
và , đồng thời từ phải chứa chữ cái phụ.
Ta nói rằng từ x dẫn trực tiếp ra từ y, ký hiệu x y, nếu tồn tại các
từ x
1
, x
2
, u, v ( V)
*
sao cho x = x
1
u x
2
, y = x


6
Ngôn ngữ L(G) sinh bởi văn phạm G đợc định nghĩa nh sau:
L(G) = { w w
*
, S
*
w}.
Văn phạm G đợc gọi là văn phạm cảm ngữ cảnh nếu mỗi quy tắc
của nó đều có dạng

1
A

2


1


2
trong đó

1
,

2
( V)
*
, A

Định nghĩa 1.7: Nguồn là một đa đồ thị có hớng gán nhãn I = (V, E, s
0
, F,
, n), gồm V là tập các đỉnh và E là tập các cung. Trên đồ thị có một đỉnh
đặc biệt s
0
gọi là đỉnh vào và đặt trong ô tròn có mũi tên, một tập con F các
đỉnh đợc gọi là các đỉnh kết thúc và đặt trong các ô hình chữ nhật. Hàm
gán nhãn n : E
{} gán cho mỗi cung của đồ thị một chữ cái thuộc
tập
{}.
Cung của nguồn I mà trên đó gán ký hiệu rỗng đợc gọi là cung
rỗng. Cung trên đó gán một chữ cái thuộc bảng chữ cái đợc gọi là cung
cốt yếu. Đỉnh có cung cốt yếu đi vào hoặc đi ra đợc gọi là đỉnh cốt yếu. Ký
hiệu tập các đỉnh cốt yếu của nguồn I là D(I).
Ngôn ngữ sinh bởi một nguồn đợc xác định nh sau:
Giả sử d = < x, s
1
, s
2
, , s
n
, y > là một đờng đi nào đó trên nguồn I. Trên
cung (x, s
1
) có nhãn là chữ cái a
1
, trên cung (s
1

19
a) N
Ii
(e) = {} và t đợc gọi là cung rỗng.
b) N
Ii
(e) = {a}, với a và e đợc gọi là cung cốt yếu.
c) N
Ii
(e) = C(L(I
j
)) và khi đó ta nói rằng cung e phụ thuộc vào đồ thị
sinh I
j
và đợc gọi là cung bù.
d) N
Ii
(e) =
I
t
k
I
k
IL
1
)(
=
, trong trờng hợp này ta nói rằng cung e phụ
thuộc vào các đồ thị sinh I
j1

j
trong sơ đồ sinh S nếu I
i

chứa một cung nào đó phụ thuộc vào đồ thị sinh I
j
hoặc phụ thuộc vào một
đồ thị có chứa cung phụ thuộc vào đồ thị I
j
. Sự phụ thuộc của các đồ thị sinh
trong một sơ đồ sinh mang tính bắc cầu và lan truyền về phía cuối dãy. Do
vậy, ta định nghĩa:
Định nghĩa 3.4: Ngôn ngữ sinh bởi sơ đồ sinh S, ký hiệu là L(S), là ngôn
ngữ sinh bởi đồ thị sinh cuối cùng I
n
trong dãy. Nghĩa là, L(S) = L(I
n
).
Để xác định đợc độ phức tạp otomat của sơ đồ sinh S, chúng ta tính
toán độ sâu độ phụ thuộc l(S) của sơ đồ này nh sau.
Giả sử e là một cung của đồ thị sinh nào đó I thuộc sơ đồ sinh S. Độ
sâu độ phụ thuộc của cung e, ký hiệu là l(e) và đợc xác định một cách đệ
quy nh sau:
1) Nếu e là cung rỗng hay cung cốt yếu thì đặt l(e) = 0.
2) Nếu e là cung bù phụ thuộc vào đồ thị sinh I' và l(I') đã xác định
thì l(e) = l(I') +1.
3) Nếu e là cung lấy tiền tố hay lấy hậu tố phụ thuộc vào đồ thị I' và
l(I') đã xác định thì l(e) = l(I') +1.
4) Nếu e là cung giao phụ thuộc vào các đồ thị sinh I
i1

trong biểu thức chính quy E đợc ký hiệu là |E|.
Định lý 3.2: Với mọi biểu thức chính quy E luôn tồn tại một nguồn I tơng
đơng với A sao cho: |D(I)| |E|.
Theo định lý trên, cận trên của độ phức tạp otomat của biểu thức
chính quy E không lớn hơn 2
|D(I)|
, trong đó D(I) là tập các đỉnh cốt yếu của
nguồn I tơng đơng.
3.3. Độ phức tạp otomat của sơ đồ sinh
3.3.1. Khái niệm sơ đồ sinh
Định nghĩa 3.2: Đồ thị sinh I = (V, E, s
0
, F, , N) trên bảng chữ cái là
một đa đồ thị (V, E) hữu hạn có hớng và có thể có đỉnh nút. Trên đồ thị
này có một đỉnh đặc biệt s
0
gọi là đỉnh vào, một tập con không rỗng các
đỉnh F gọi là tập đỉnh ra. Hàm gán nhãn N : E 2

*
gán cho mỗi cung của
đồ thị một tập các từ trên bảng chữ cái .
Khái niệm đồ thị sinh là mở rộng thực sự của khái niệm nguồn.
Giả sử d = e
1
, e
2
,

, e

là tập tất cả các từ sinh bởi mọi
đờng đi trên đồ thị sinh I đi từ đỉnh vào s
I
. Tập L(I) đợc gọi là ngôn ngữ
sinh bởi đồ thị sinh I.
Định nghĩa 3.3: Sơ đồ sinh trên bảng chữ cái là một dãy các đồ thị sinh
trên , S = (I
1
, I
2
, , I
n
) thoả mãn ba tính chất sau đây:
1. Các đồ thị sinh I
1
, I
2
, , I
n
từng đôi một không có đỉnh chung.
2. Với mỗi cung e của đồ thị sinh I
i
(1 i n) thuộc S thì một trong các đẳng
thức sau đợc thoả mãn: 7
2) Nếu từ w L
I
(x, z) và từ đỉnh z sang đỉnh y có cung với nhãn là

Cs
II
U

. Tập này chính
là tập các đỉnh cốt yếu kề với đỉnh thuộc C nhờ các cung có nhãn là a.
Bây giờ ta xây dựng nguồn đơn định K nh sau:
Đỉnh vào của K là đỉnh {s
0
} với s
0
là đỉnh vào của nguồn I. Với mỗi đỉnh C
D(I) ta xác định H
I
(C, a) và vẽ một cung đi từ đỉnh C sang đỉnh H
I
(C, a)
với nhãn là chữ cái a. Tập đỉnh kết thúc F(K) = {C V(I) C

F(I)

}.
Với cách xây dựng trên thì nguồn K là đơn định, đầy đủ và tơng
đơng với nguồn I đã cho.
Định nghĩa 1.9: Nguồn K trên bảng chữ cái sinh ra ngôn ngữ là phần bù
của ngôn ngữ L(I) đợc gọi là nguồn bù của nguồn I.
Thuật toán 1.7 (Xây dựng nguồn bù)
Ta đổi tất cả các đỉnh không kết thúc thành đỉnh kết thúc và ngợc
lại đổi đỉnh kết thúc thành đỉnh không kết thúc thì nguồn nhận đợc sẽ sinh
ngôn ngữ bù của ngôn ngữ sinh bởi nguồn ban đầu.

, C
2
), trong đó C
1
D(I
1
), C
2
D(I
2
) là các tập
con các đỉnh cốt yếu và a là chữ cái thuộc . Khi đó, ta xác định đỉnh C =
(H
I1
(C
1
,a), H
I2
(C
2
,a)) và thêm một cung đi từ đỉnh B sang đỉnh C với nhãn là
chữ cái a.
3) Đỉnh (S, R) nào đó trong tập đỉnh của nguồn I vừa xây dựng đợc
xem là đỉnh kết thúc khi và chỉ khi: S F(I
1
) và R F( I
2
) . Với
thúc của nguồn I
2
là các đỉnh kết thúc của nguồn I. Đồng thời, từ mỗi đỉnh
kết thúc của nguồn I
1
ta vẽ một cung rỗng đi tới đỉnh vào của nguồn I
2
.
Với cách xây dựng nh trên, ngôn ngữ sinh bởi nguồn I là tích
ghép của ngôn ngữ đợc sinh bởi nguồn I
1
và nguồn I
2

c) Otomat hữu hạn và ngôn ngữ đợc đoán nhận bởi otomat hữu hạn
Định nghĩa 1.10: Otomat hữu hạn đơn định trên bảng chữ cái là một bộ
năm: A = (Q, , q
0
, , F), trong đó:
- Q là một tập hữu hạn các trạng thái,
- là bảng chữ cái vào,
- : Q ì
Q , đợc gọi là hàm chuyển trạng thái,
- q
0
Q , đợc gọi là trạng thái khởi đầu,
- F Q , đợc gọi là tập trạng thái kết thúc của otomat.
Mỗi lần chuyển trạng thái trong otomat hữu hạn đơn định ta chỉ
nhận đợc một trạng thái kế tiếp. Ta mở rộng hàm chuyển thành ánh xạ
: Q ì

Định nghĩa 1.13: Otomat hữu hạn A đợc gọi là đầy đủ nếu hàm chuyển
trạng thái xác định khắp nơi trên tập Q ì . Nghĩa là: 17
Đầu ra: Đồ thị phủ rút gọn của hệ mạng vị trí - chuyển .
1) Xây dựng đồ thị phủ cho hệ mạng vị trí - chuyển có nhãn trên cạnh
là các bớc đơn (Thuật toán 3.2).
2) Nếu (V
1
, U
1
, V
2
) và (V
1
, U
2
, V
3
) là các cạnh của đồ thị với U
1
U
2
=
và 0 V
2
+ U
2
K, tập U = U

= V
2
+ U
2
, và
thêm vào cạnh mới (V
1
, U, V
4
).
3) Lặp lại các bớc 2) chừng nào còn có thể.
Dãy các nhãn trên các đờng đi của đồ thị rút gọn vừa nhận đợc
sẽ cho ta các quá trình tơng tranh của mạng với các bớc tơng tranh
cực đại.
Độ phức tạp của thuật toán: Độ phức tạp của thuật toán là O(n.|T|
4
), với n là
số đỉnh của đồ thị phủ.

Chơng 3. Độ phức tạp otomat của các thuật toán
đoán nhận ngôn ngữ
Số trạng thái của otomat
đơn định có ít trạng thái nhất đoán nhận
một ngôn ngữ đợc gọi là độ phức tạp otomat
của ngôn ngữ.

3.1. Độ phức tạp otomat của nguồn
Giả sử = {a
1
, a

(r) . (s) là biểu thức chính quy biểu diễn ngôn ngữ R . S , 16
Định lý 2.7 : Giả sử là đồ thị phủ của hệ mạng vị trí - chuyển . Với mỗi
dãy hoạt động M
0
[t
1
> M
1
[t
2
> M
2
. . . M
k-1
[t
k
> M
k
trên hệ mạng luôn tồn
tại một đờng đi < V
0
t
1
V
1
t
2

t
1
t
1


=

t
2
t
2


=


t
1


t
2
=

t
1
t
2



: M(p) K(p) - ),( ptW
Ut


.
Hiển nhiên, tập con các chuyển U là một bớc khi và chỉ khi U là
tách đợc và tồn tại bộ đánh dấu M thoả mãn: 0 M + U
K.
2.3.3. Tìm bớc tơng tranh bằng cách rút gọn đồ thị phủ
Các kết quả dới đây là cơ sở cho việc rút gọn đồ thị phủ.
Định lý 2.8 : Giả sử là một hệ mạng vị trí - chuyển, các bộ đánh dấu V
2
,
V
3
R(V
1
), hai tập con các chuyển U
1
, U
2
không giao nhau. Nếu (V
1
, U
1
,
V
2
) và (V

2
+ U
2
, cũng thuộc đồ thị phủ và V
1
[ U > V
4
.
Định lý 2.9 : Giả sử là một hệ mạng vị trí - chuyển, các bộ đánh dấu V
2
,
V
3
R(V
1
), hai tập con các chuyển U
1
, U
2
không giao nhau. Nếu (V
1
, U
1
,
V
2
) và (V
2
, U
2

Các kết quả trên đợc minh hoạ qua hình vẽ dới đây: Dựa vào các kết quả trên, chúng ta xây dựng thuật toán nh sau.
Thuật toán 2.3 (Rút gọn đồ thị phủ)
Đầu vào: Hệ mạng vị trí - chuyển = (P, T; F, K, M
0
, W). 9

q Q,

a

đều có (q,a) .
Giả sử A = (Q, , q
0
, , F) là một otomat hữu hạn không đơn định
và không đầy đủ. Ta xây dựng otomat A hữu hạn, đơn định và đầy đủ tơng
đơng với A nh sau:
i) Để xây dựng hàm chuyển cho otomat đơn định A ta xây dựng
hàm hai biến T
A
: 2
Q
ì 2
Q
nh sau:

định nh sau: q
Q , a , f(q,a) = T
A
(q',a).
Với cách xây dựng nh trên, dễ dàng chỉ ra rằng otomat A là
otomat
hữu hạn đơn định đầy đủ và L(A) = L(A).
d) Sự tơng đơng giữa nguồn và otomat hữu hạn
Từ mỗi nguồn I ta đều có thể xây dựng một otomat hữu hạn A
tơng đơng với nó và ngợc lại.
Thuật toán 1.10 (Xây dựng otomat tơng đơng với nguồn)
1) Xây dựng hàm T
I
: 2
D(I)
ì 2
D(I)
nh sau:
- a : T
I
( ,a) = ,
- s (D(I) {s
0
}), a : T
I
({s},a) = {s' D(I) a L
I
(s,s')},
- q D(I), a : T
I


q Q,

a : (q,a) = T
I
(q,a)
Otomat A tơng đơng với nguồn I đã cho. Bây giờ ta thực hiện điều ngợc
lại.
Thuật toán 1.11 (Xây dựng nguồn tơng đơng với otomat)
1) Lấy các điểm trên mặt phẳng tơng ứng với các trạng thái của
otomat và đặt tên cho các điểm này bằng các ký hiệu trạng thái của otomat
A. Đỉnh vào của nguồn I là trạng thái khởi đầu của otomat. Đỉnh đợc xem
là đỉnh kết thúc của nguồn khi trạng thái của otomat A tơng ứng với nó là
trạng thái kết thúc. 10
2)

q, q' Q , a : có cung nối từ đỉnh q sang đỉnh q' gán
nhãn là ký hiệu a q'
(q,a).
Nguồn I nhận đợc tơng đơng với otomat A đã cho.

1.3. Hệ Mạng
Hệ mạng là một mô hình toán học thờng đợc dùng để biểu diễn
các hệ thống phân tán.
1.3.1 Mạng Petri
Định nghĩa 1.14: Bộ ba N = (S, T; F) đợc gọi là một mạng Petri nếu:
1) S và T là hai tập hợp không giao nhau.


đợc gọi là trờng hợp kế tiếp của c. Hay nói một cách
khác, c chính là kết quả thực hiện biến cố e.
Ta ký hiệu: c [ e > c.
Không gian các trạng thái của hệ là môi trờng để dãy các bớc có thể xảy
ra trên hệ, tạo nên các quá trình trên hệ.
Định nghĩa 1.17:
1) Quan hệ r
N
2
B
ì 2
B
đợc định nghĩa nh sau:
(c
1
, c
2
) r
N
e E : c
1
[ e > c
2
, gọi là quan hệ đạt đợc tiến trên
mạng N.
2) Quan hệ R
N
= (r
N

1
, c
2
, c
3
, , c
m
phải thuộc lớp tơng đơng của quan hệ đạt
đợc R
N
chứa c
0
. Các biến cố e
1
, e
2
, e
3
, , e
m
xuất hiện một cách tuần tự
trong chính lớp tơng đơng này. 15
2) Nếu (c
1
, G
1
, c

3) Nếu (c
1
, G
1
, c
2
) và (c
2
, G
2
, c
3
) là các cạnh của đồ thị và G = G
1
G
2
là
tách đợc thì ta thêm vào một cạnh mới (c
1
, G, c
3
).
4) Lặp lại các bớc 2) và 3) chừng nào còn có thể.
Theo thuật toán trên, sau mỗi lần ghép cạnh có nhãn G
1
và G
2
ở
bớc 2) hoặc 3) ta bổ sung thêm cạnh mới với bớc tơng tranh G = G
1

Thuật toán 2.2 (Xây dựng đồ thị phủ)
Đầu vào: Hệ mạng vị trí - chuyển = (P, T; F, K, M
0
, W).
Đầu ra: Đồ thị phủ của hệ mạng vị trí - chuyển .
1) Xây dựng đồ thị ban đầu chỉ gồm một đỉnh V
0
= M
0
, không có cung.
2) Giả sử V là đỉnh nào đó của đồ thị nhng cha có cung nào đi ra từ nó
thì:
1. Nếu V kích hoạt chuyển t nào đó và V[ t > V thì ta bổ sung đỉnh
mới V và cung mới (V, t, V) vào đồ thị.
2. Trên đờng từ đỉnh V
0
tới đỉnh V, nếu tồn tại đỉnh V mà V' < V
thì với những vị trí p mà V(p) < V(p) thì toạ độ tơng ứng của V
đợc thay bằng và đỉnh V đợc gọi là

-đỉnh.
3. Trên đờng từ đỉnh V
0
tới đỉnh V, nếu tồn tại đỉnh V mà V' = V
thì V là đỉnh treo của đồ thị.
4. Nếu không có một chuyển nào đợc V kích hoạt thì V là đỉnh treo.
3) Lặp lại bớc 2) chừng nào còn có thể. 14

1
, c
2
)
N
r

G E : c
1
[ G > c
2
.
2) Quan hệ
N
R = (
N
r
N
r
-1
)
*
là một quan hệ tơng đơng trên tập 2
B
và
đợc gọi là quan hệ đạt đợc đồng thời trên hệ mạng .
Dễ dàng chứng minh rằng, quan hệ đạt đợc và quan hệ đạt đợc
đồng thời là bằng nhau. Nh vậy, sự tuần tự đang ẩn chứa sự tơng tranh.

2.2.3. Đầy đủ hoá đồ thị các trờng hợp

2
và c
1
[ G
2
> c
3
. Nếu G
1
G
2
= và G = G
1

G
2
là tách đợc thì c
2
[ G
2
> c
4
, c
3
[ G
1
> c
4
và c
1

2
[ G
2
> c
3
thì G
1
G
2
= và nếu G = G
1
G
2

là tách đợc thì c
1
[ G > c
3
.
Dựa vào Định lý 2.5 và Định lý 2.6, chúng tôi đa ra thuật toán làm
đầy đủ đồ thị các trờng hợp nh sau.

Thuật toán 2.1 (Đầy đủ đồ thị các trờng hợp)
Đầu vào: Hệ mạng điều kiện - biến cố = (B, E; F, C).
Đầu ra: Đồ thị các trờng hợp đầy đủ của hệ .
1) Xây dựng đồ thị các trờng hợp = (C, P) với nhãn trên cạnh là các
bớc đơn. 11

, . . ., e
m
E, c
1
, c
2
, c
3
, . . ., c
m
C
: c
0
[ e
1
> c
1
[ e
2
> c
2
[ e
3
> c
3
. . . [ e
m
> c
m
}.

của mạng.
- M
0
: P {0, 1, 2, 3, , }, là bộ đánh dấu đầu tiên của mạng phù
hợp với dung lợng, có nghĩa là: p P : M
0
(p) K(p).
Quy luật hoạt động trên hệ mạng vị trí - chuyển đợc mô tả nh sau:
Định nghĩa 1.22:
1) ánh xạ M : P {0, 1, 2, 3, , } đợc gọi là một bộ đánh dấu của
mạng nếu: p P : M(p) K(p).
2) Giả sử M là một bộ đánh dấu.
- Chuyển t T đợc gọi là M-kích hoạt nếu:
p

t : M(p) W(p, t) và p t

: M(p) K(p) - W(t, p).
- Một chuyển M-kích hoạt t hoạt động sẽ cho ta bộ đánh dấu kế
tiếp M của M đợc xác định nh sau: 12
M(p) =







(p) =









0
),(),(
),(
),(
tpWptW
ptW
tpW

ii) Xây dựng ma trận N
: P ì T Z với: N(p,t) = t(p).
Công thức ngắn gọn cho quy luật hoạt động trên hệ mạng nh sau:
M [ t > M ( 0 M + t
K ) ( M = M + t ).
Ngôn ngữ sinh bởi một hệ mạng vị trí - chuyển là tập:
L() = { t
1
t
2
t
3

2
[ t
3
> M
3
. . . [ t
n
> M
n
}.
Lớp các ngôn ngữ sinh bởi các hệ mạng vị trí - chuyển là tập con của lớp
các ngôn ngữ cảm ngữ cảnh và chứa lớp các ngôn ngữ phi ngữ cảnh.

Chơng 2. Các thuật toán điều khiển trên hệ mạng
và độ phức tạp của chúng
2.1. Bài toán điều khiển tơng tranh các quá trình
Với mỗi hệ thống nào đó thì hành vi của nó mô tả những gì mà hệ
thống đó có thể thực hiện đợc. Hành vi của một hệ thống bao gồm các quá
trình xảy ra trên hệ. Các quá trình đợc phân thành hai loại sau đây:
1) Quá trình tuần tự: là quá trình mà các hành động trong nó đợc
thực hiện kế tiếp nhau.
2) Quá trình tơng tranh: là quá trình mà trong nó có nhiều hành
động có thể đợc thực hiện song song với nhau,
, nếu p

t \ t


, nếu p t


quá trình tối u.
Bài toán điều khiển tơng tranh các quá trình
Với một hệ thống đã cho, hãy xây dựng thuật toán để biến đổi các
quá trình tuần tự của một hệ thống thành các quá trình tơng tranh tối u
tơng ứng. Sơ đồ biến đổi tơng tranh đợc thể hiện nh hình vẽ dới đây:

Việc giải quyết bài toán điều khiển này không những chỉ ra cho chúng ta
một cách thực hiện tối u các quá trình xảy ra trên hệ thống mà còn giúp
tìm ra hành vi tơng tranh của hệ.
2.2. Thuật toán điều khiển tơng tranh trên các hệ mạng điều
kiện - biến cố
2.2.1. Đồ thị các trờng hợp
Để có cái nhìn tổng quát tất cả các quá trình xảy ra trên một hệ mạng điều
kiện - biến cố, ta xây dựng đồ thị các trờng hợp của hệ này.
Định nghĩa 2.1: Đa đồ thị định hớng, gán nhãn = (C, P), với tập đỉnh là
tập các trờng hợp C của hệ mạng và tập cạnh P = {(c, e , c') C

ì E ì C

c

[ e > c'} đợc gọi là đồ thị các trờng hợp của hệ mạng .
Định lý 2.1: Mọi đồ thị các trờng hợp của các hệ mạng điều kiện - biến cố
đều liên thông và không có đỉnh nút.
Định lý 2.2: Hệ mạng điều kiện - biến cố là chu trình khi và chỉ khi đồ
thị các trờng hợp của nó là liên thông mạnh.
Định lý 2.3: Hệ mạng điều kiện - biến cố là sống khi và chỉ khi với mỗi
trờng hợp c C

và với mỗi biến cố e E đều có đờng đi c l

e
2
= e
1

e
2

=
e
1

e
2
=

e
1
e
2

= .
2) Giả sử c và c' là các trờng hợp của hệ mạng điều kiện - biến cố
và tập các biến cố G là tách đợc. G đợc gọi là một bớc tơng
tranh từ c tới c' nếu và chỉ nếu mỗi biến cố e trong G là c-kích hoạt
và c' = (c \