TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 KHOA TOÁN
PHAN THỊ HƯỚNG
MỐI LIÊN HỆ GIỮA ĐẠI số, ÔTÔMAT VÀ LOGIC
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành:TOÁN ỨNG DỤNG
Người hướng dẫn khoa học
GS. TRẦN VĨNH ĐỨC
LCU CAM ON
Em xin bay to long biet dn sau sac tdi thay Tran Vinh Du”c - NgiicJi
thay da trtfc tiep tan tinh hildng dan va giup dd em hoan thanh bai khoa
luan cua minh. Dong thcJi em xin chan thanh cam dn cac thay co trong to
Ling dung va cac thay co trong khoa Toan - TrUdng Dai hoc Sii pham Ha
Noi 2, Ban chu nhiem khoa Toan da tao dieu kien cho em hoan thanh tot
bai khoa luan nay.
Trong khuon kho co han cua mot bai khoa luan, do dieu kien thcJi gian,
do trinh do co han va cung la lan dau tien nghien ciiu khoa hoc cho nen
khong tranh khoi nhiing han che, thieu sot nhat dinh. Vi vay, em kinh
mong nhan diidc nhiing gop y cua cac thay co va cac ban.
Em xin chan thanh cam dn !
Ha Noi, thdng 05 ndm 2014 Sinh vien
Phan Thi Hif6ng
LOl CAM DOAN
Khoa luan nay la ket qua cua ban than em trong qua trinh hoc tap va
nghien ctiu. Ben canh do em dildc svt quan tarn cua cac thay co giao trong
khoa Toan, dac biet la sii hiidng din tan tinh cua TS.Tran Vinh Dilc.
Trong khi nghien ciiu hoan thanh khoa luan nay em da tham khao mot
so tai lieu da ghi trong phan tai lieu tham khao.
Em xin khang dinh ket qua cua de tai “Moi lien he gifla dai so, otomat
va logic” khong co sii trung lap vdi ket qua cua cac de tai khac.
Ha Noi, thdng 05 ndm 2014
Sinh vien
17
2
8
29
30
29
3
3
3
6
41
42
Một số phép toán trên ngôn ngữ
Otomat
1.4.1.
1.4.2.
Chương 2.
2.1.
2.2.
Chương 3.
3.1.
3.2.
3.3.
3.4.
3.5.
Thuật toán tính toán otomat tối tiểu
Vị nhóm chuyển của ôtômat
VỊ nhóm cú pháp
Kết luận
Khóa luận gồm:
Chương 1. Ô tômat và logic.
Chương 2.Định lý K Ỉ E E N E — B Ử C H I .
Chương 3.Ôtômat tối tiểu và vị nhóm cú pháp.
Chương 1
Otomat và logỉc
1.1. Bảng chữ, từ và ngôn ngữ
B Ả N G C H Ữ C Á I là một tập hữu hạn khác rỗng. Mỗi phần tử của bảng chữ cái
được gọi là một chữ cái hay một ký hiệu. Một T Ừ trên bảng chữ cái A là một dãy hữu
hạn (gồm một số lớn hơn hoặc bằng không) chữ cái của A .
ví dụ 1.1. Tập A = { A , B , C } là một bảng chữ cái và A A B A C B A là một từ trên A .
Độ dài của một từ W , ký hiệu là |w| là số các chữ cái trong W . Ví dụ, Ị A B C A Ị =
4 . Từ không chứa ký hiệu nào gọi là từ rỗng và ký hiệu là E . Theo định nghĩa |e| = 0.
Tập hợp gồm tất cả các từ trên bảng chữ cái A được ký hiệu là A * , và tập hợp gồm tất
cả các từ khác rỗng trên bảng chữ cái A được ký hiệu là A
+
. Rõ ràng
A
+
=A*-{e}.
3
Xét hai từ U và V trên bảng chữ A , phép ghép hai từ này là từ U V tạo được bằng cách
đặt V liền ngay sau u. Rõ ràng phép ghép có tính chất kết hợp và không giao hoán trên
A * (trừ khi bảng chữ A chỉ gồm một phần tử). Dễ thấy, ghép của hai từ có tính chất
sau:
|hv| = \u\ + I vỊ
u£ = £u = u
ngữ) trên bảng chữ cái A . Tập rỗng 0 là ngôn ngữ trên mọi bảng chữ cái: ngôn ngữ
không chứa một từ nào. Chú ý rằng ngôn ngữ rỗng 0 khác với ngôn ngữ chỉ gồm một từ
rỗng {e}.
п> 0
Nếu A và В là các bảng chữ cái, một đồng cấu từ A * đến B * là một ánh xạ Ẹ thoả
mãn hai điều kiện
3
ư = <
1. <p(e) = e
2. Vu,V G А*, Ф (uv) = Ç (U )Ç (v)
Để xác định một đồng cấu như trên, ta chỉ cần xác định ảnh của các chữ cái của A qua
Ф. Ảnh của mỗi từ , U = 0102 -0/1 € A * thu được bằng cách ghép ảnh của các chữ,
có nghĩa rằng
ẹ{u) = ẹ{a{]ẹ{a
2
) ẹ{a
n
).
. Phép toán này mở rộng một cách tự nhiên cho ngôn ngữ bằng cách đặt
ẹ (L) = {ẹ (и) I и € L}
với mỗi ngôn ngữ L ç A * .
Nghiên cứu các phép toán cơ bản hợp, ghép và lặp trên ngôn ngữ đưa ta đến định
nghĩa tự nhiên của lớp ngôn ngữ chính quy. Các phép toán này được gọi là các phép
toán chính quy. Một ngôn ngữ trên bảng chữ cái A được gọi là chính quy nếu nó có
thể thu được từ các chữ cái của A bằng cách áp dụng (một số hữu hạn) các phép toán
chính quy. Định nghĩa hình thức như sau.
Lớp các ngôn ngữ chính quy trên bảng chữ cái A , ký hiệu RatA*, là lớp nhỏ nhất các
ngôn ngữ được định nghĩa bởi
1. Ngôn ngữ 0 và {a} là chính quy, với mỗi chữ cái A G А .
2. Nếu К và L là các ngôn ngữ chính quy thì K \ J L , K L và L * cũng là chính quy.
Ví dụ 1.3. Xét các ngôn ngữ sau.
3
• Ngôn ngữ
Ữ
, A I , Q I ) (qi,a
2
,q2) • ■ •
(Q
N
- \ , A
N
, Q
N
) cũng được thể hiện bởi dãy mũi tên
P =
q ữ
a
-\
q i
a
ìqi
a
-$qr,
Ta nói P là một đường đi có độ dài N từ <70 đến Q
N
gán nhãn bởi từ từ U = A I A 2- - - -
A
N
. Theo định nghĩa, mỗi trạng thái Q , tồn tại một đường đi rỗng từ Q đến Q gán nhãn
bởi từ rỗng.
Ví dụ 1.6. Trong otomat ở hình|l.lị từ A
3
B A là nhãn của đúng 4 đường đi: từ 1 đến 1, từ 1
C O M P
là đủ và L (A
comp
) = L (Л).
Chúng ta có thể thấy rằng trên sự làm đầy A
C O M P
của một otomat không đầy đủ A ,
trạng thái Z không thuộc đường đi thành công nào: nó là trên một con đường trạng thái vô
ích. Ngược lại với Otomat đầy, otomat rút gọn là otomat bỏ đi các trạng thái vô ích giúp
cho thiết bị gọn hơn.
Một trạng thái Q của một otomat A được nói là đạt được nếu tồn tại một đường đi trên
A bắt đầu từ một trạng thái ban đầu và kết thúc tại Q . Trạng thái Q gọi là đối đạt được nếu
tồn tại một đường đi trong A bắt đầu từ Q và kết thúc tại một trạng thái chấp nhận. Một
trạng thái là cả đạt được và đối đạt được nếu và chỉ nếu nó nằm trên ít nhất một con đường
thành công.
Một otomat được gọi là rút gọn nếu tất cả các trạng thái là đạt được và đối đạt được. Có
nghĩa rằng, trong otomat rút gọn, mọi trạng thái là đều có ích: nó được sử dụng để chấp
nhận một số từ thuộc ngôn ngữ L ( A ) . Tất nhiên, mỗi otomat
A là tương đương với một otomat rút gọn, ta viết A T R I M là otomat thu được từ S Ể bằng
cách loại bỏ các trạng thái không đạt được hoặc không đối đạt được và các chuyển liên
quan.
Để thuận tiện ta cũng xem xét một mở rộng định nghĩa của otomat cho £ — otomat. Sự
khác biệt cơ bản so với otomat thông thường là E — otomat cho phép chuyển có nhãn E ,
tức chuyển có dạng (P , E , Q ) với P , Q G Q .
Một otomat A = (Q , T , I , F ) được gọi là đơn định nếu nó có đúng một trạng thái bắt
đầu, và với mỗi chữ cái A và các trạng thái Q , Q ' , Q " , điều kiện
{q,a,q'), (<ĩ,a,q”) e T
chỉ ra rằng Q ' = Q ” .
Mệnh đề 3.1. Cho A là một otomat đơn định và w là một từ.
1. Với mỗi trạng thái q của A, đều tồn tại ít nhất một đường đi gán
{PQQ\PnF ^ф}.
Do cách xây dựng, otomat A
s u
b là đơn định và đầy đủ, và hàm chuyển tập con của A là
hàm chuyển A
S U
P . Hơn nữa, nếu A C Ó N trạng thái, thì A
S U
P có 2" trạng thái.
Mệnh đề 3.3. Otomat A và A
s u
b là tương đương.
C H Ứ N G M I N H . Cho A = (Q , T , I , F ). Ta chứng minh bằng quy nạp theo |w| rằng,
với mọi P Ç Q và W E A * , giá trị 5 (p,w) là tập hợp mọi trạng thái Q E Q thoả mãn W
gán nhãn bởi một đường đi trên A bắt đầu tư một vài trạng thái trong P và kết thúc tại Q .
Do đó, một từ W được chấp nhận bởi Л nếu và chỉ nếu ít nhất một trạng thái kết thúc
nằm trong tập <5 ( I , W ) , nếu và chỉ nếu <5 ( I , W ) € F
S U
Ị , nếu và chỉ nếu W được chấp
nhận bởi A
S U
B - Đây là điều phải chứng minh. □
5(Q,UA) = <
1.4. Logic: Tính toán dãy của Bũchi
Ta bắt đầu bằng một ví dụ.
Ví dụ 1.9. Nhớ lại rằng Л là phép hội, đọc là ’’AND” và V là phép tuyển, đọc là " OR".
Chúng ta sẽ xem xét công thức kiểu như sau
ЗхЗу (x < y) A R
a
x Л Rf,y.
Biến xuất hiện sau một lượng từ (tồn tại hoặc phổ dụng): sự xuất hiện của các biến số
trong phạm vi của lượng từ được gọi ràng buộc. Các xuất hiện khác gọi là tự do. Một định
nghĩa (chính xác), đệ quy của tập biến tự do F V (< P ) của công thức Ẹ như sau:
• Nếu Ẹ là nguyên thuỷ, sau đó F y ( < P ) là tập mọi biến các biến số xuất hiện trong
Ẹ ,
• F V ( ф) = F V (<p)
• F V (<p Л vO = F V (ф V vO = F V ( Ọ ) V F V ( Ự )
• F V ( Ix ẹ ) = F V (Vx<p) = F V (9) \ {x }
Một số công thức không có biến tự do được gọi là một câu.
Diễn dịch của công thức
Trong tính toán dãy Biichi, các công thức được diễn dịch trong các từ: mỗi từ И có độ
dài N > 0 xác định một cấu trúc (mà chúng ta viết ngắn gọn tuy không hoàn toàn chính
xác là И ) với miền D O M (И ) = (0, . . . , N — 1) ( D O M (и) = 0 nếu И = E ) . D O M
(и) được xem như tập các vị trí trong từ И (được đánh số từ 0). Ký hiệu < được diễn dịch
trong D O M (и) như thứ tự thông thường (như (2 < 4) và -I (3 < 2) ). Ký hiệu 5 được giải
thích như các ký hiệu liền sau: Nếu X , Y E D O M . ( U ) , vậy S (X , У ) nếu và chỉ nếu У
= X + 1. Cuối cùng, với mỗi chữ cái А e A , ký hiệu quan hệ một ngôi R
A
được diễn dịch
như tập các vị trí trong И mang một ký hiệu А (đây là một tập con của D O M (и)).
Ví dụ 1.10. Nếu И = A B B A A B , vậy D O M { И ) = {0,1, , 5}, R
A
= {0,3,4} và ** =
{1,2,5}.
Một sự đánh giá trên И là một ánh xạ V từ một tập các giá trị vào miền D O M (и).
Nó sẽ hữu ích để có một ký hiệu cho sự thay đổi nhỏ của một đánh giá. Nếu V là một
đánhgiá và D là một phần tử của D O M (и), ta đặt V [* !-»•Đ \ là đánh
giá v' xác định bằngcách mở rộng miền của V bao gồm cả giá trị X và đặt
V (у ) nếu у Ф X d nếu у = X
Nếu Ẹ là một công thức, И E A * và V là một đánh giá trên И mà
và cùng kéo theo: <p — > Ự thay cho -|<P V 1/A và <p Ự thay cho (p-> VOMV'-» 9).
yí dụ 1.11. Cho ( P và Y / được cho bởi công thức sau
<p = 3 X ((Vy-I ( Y < *)) A R
A
X )
Y Ự = \ / X ((Vy-I ( Y < *)) — >
R
A
X )
Câu ( P khẳng định rằng có tồn tại một vị trí mà không có phần tử trước nó chứa A , trong
khi đó \ Ự khẳng định rằng mọi vị trí như vậy đều chứa một A . Sau một câu, giống như tất
cả các phép lượng hóa phổ dụng câu bậc nhất, là rỗng thỏa mãn bởi xâu rỗng. Do đó L
( Ọ ) = A A * và L (1Ự ) = A A * u {e}.
Logic bậc nhất của thứ tự tuyến tính (tương ứng của các phần tử tiếp sau), viết F O (<)
(tương ứng là FO(S)) là phần logic bậc nhất mô tả trước, nhưng trong các công thức không
dùng ký hiệu S(tương ứng <).
1.4.2. Công thức monadic bậc hai
Trong logic monadic bậc hai, chúng ta thêm một kiểu biến logic mới vào logic bậc
nhất, gọi là biến tập và thường được ký hiệu bởi chữ cái in hoa, ví dụ:
X , Y , __Công thức nguyên tử của monadic bậc hai là công thức nguyên thủy
của logic bậc nhất, và các công thức có dạng (Xj), ở đó X là một biến tập và Y là một biến
thông thường.
Định nghĩa đệ quy của công thức monadic bậc hai, bắt đầu từ các công thức nguyên
thủy, gần giống như công thức bậc nhất: nó sử dụng cùng các quy tắc và thêm quy tắc mới:
• Nếu ( P là công thức monadic bậc hai và X là một biến tập, thì (3*<p) và V X < P là
các công thức monadic bậc hai.
Khái niệm của các biến tự do được mở rộng tương tự.
Diễn dịch của công thức monadic bậc hai cũng yêu cầu mở rộng của định nghĩa của
đánh giá trên một từ U : một đánh giá monadic bậc hai là một ánh xạ
V gắn mỗi biến bậc nhất một phần tử của miền D O M (U ), và mỗi biến tập, một tập
trí thuộc X nếu và chỉ nếu vị trí tiếp theo không thuộc X (do đó X chứa các vị trí cách
nhau một), và vị trí đầu tiên là trong X , và vị trí cuối cùng là không trong X . Do đó L(<p)
là tập hợp các từ có độ dài chẵn. Ngôn ngữ này không mô tả được bằng công thức bậc nhất.
Quan hệ kế tiếp có thể được biểu thị trong F O ( < ) : S ( X , Y ) tương đương logic với
công thức sau:
( x < y ) AV z ( ( * < z ) - > ((y = z) V (y < z)))
NgứỢc lại, quan hệ thứ tự < là có thể được biểu thị trong MSO(S): Công thức tương đương
logic với công thức:
3 X (XyA^XxA [VzVí((XzAS(z,í)) -> Xf)D
Sau đó M S O (<) và M S O ( S ) có cùng khả năng biểu diễn.
Mệnh đề 4.1. Một ngôn ngữ có thể được định nghĩa bởi một câu trong
MSO(S) nếu và chỉ nếu nó có thể được định nghĩa bởi một câu trong
MSO(<).
Tuy nhiên, quan hệ thứ tự < không thể được biểu thị trong F O ( S ) . Đây là một kết
quả không tầm thường.
Mệnh đề 4.2. Nếu một ngôn ngữ được định nghĩa bởi một câu trong FO(S )
vậy nó có thể được định nghĩa bởi một câu trong FO(<). Nhưng ngược lại
không đúng.
Chương 2
Đinh lý Kleene-Bũchi
Mục đích của chương này là chứng minh của định lý sau, là kết hợp của cả định lý
Kleene và định lý Bủchi.
Định lý 2.0.1. Xét L là một ngôn ngữ trong A*. Các điều kiện sau là tương
đương:
1. L được định nghĩa bởi một câu trong MSO(<);
2. L được đoán nhận bởi otomat;
3. L là chính quy mở rộng;
4. L là chính quy.
2.1. Từ otomat đến công thức monadic bậc hai
Cho A = ( Q , I , 8 , F ) là một otomat đơn định. Ý tưởng ở đây là gắn mỗi mỗi trạng
phải xem xét hội câu này các câu này với câu 3 X true.
Đây là một câu trong M S O ( S , < ) nhưng như chúng ta biết, nó là tương đương logic
với M S O ( < ) . Lưu ý rằng thực ra nó là một câu monadic bậc hai chỉ chứa lượng từ tồn
tại.
2.2. Từ các công thức đến biểu thức chính quy mỏ rộng
Chứng minh rằng một ngôn ngữ có để định nghĩa bởi M S O (<) cũng được định nghĩa
bởi một biểu thức chính quy mở rộng phức tạp hơn. Lập luận bằng quy nạp trên định nghĩa
đệ quy của cộng thức. Thay vì gắn một ngôn ngữ chỉ với các câu (các công thức không có
biến tự do), chúng ta sẽ gắn các ngôn ngữ với tất cả các công thức nhưng các ngôn ngữ ở
đây sẽ trên bảng chữ cái lớn để cho phép ta mã hóa các biến.
Các bảng chữ cái phụ B P Q
Cho P , Q > 0 và cho B P Q = A X {о, \ }
P
X {0, \ }
Q
. Một từ trên bảng chữ cái B P
Q có thể đồng nhất với một dãy
{ U Q , U \ , . . . , U p , U p - 1-1, Up - ị - q )
ở đó Mo € А * , M , . . . , U
P
, U
P +
1, . . . , U P
+ Q
e {0,1}* và mọi U Ị đều có cùng độ
dài.
Cho K P Q bao gồm từ rỗng và các từ trong B P
Q
sao cho mỗi thành phần U I , . . . , U
P
} u rì (Bp,q\Ci) Ci(B
P í
q\Ci)
1
<i<p
= K,,\ и
1
<ì<p
Ngôn ngữ gắn với công thức
Bây giờ xét
ọ (xị, ,x
r
,X\,
là một công thức với các biến bậc nhất (tương ứng biến tập) tự do là Xi, ,x
r
(tương ứng là X Ị , X 2, với R < P và S < Q .
Chúng ta diễn dịch.
• R
A
như R
A
= { I e D O M (и) I Mo (ỉ) = ù};
• X ị như vị trí duy nhất của 1 trong Mị (nếu Mị Ỷ e);
• X J như tập vị trí của 1 trong U P
+
J .
Để ý rằng nếu P = Q = 0, thì <p là một câu và đây là ký hiệu thông thường trong d i ễ n
d ị c h .
H ì n h t h ứ c h ơ n , x é t ( m o , w i , . . . , U p
Vậy thì FV (<p) = {y}. Và Lio(<p) là tập các cặp từ (wO)Wi) thoả mãn
UQ € A*,U\ € {0,1}*, Щ và Mi có độ dài giống nhau, Mi chỉ
có một 1 nhưng ở vị trí đầu tiên, và
UQ
có một
a ở
vị trí này.
Copyright: Tài liệu đại học ©