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

Hà Nội - 2014


LỜI CẢM ƠN

Em xin bày tỏ lòng biết ơn sâu sắc tới thầy Trần Vĩnh Đức - Người thầy đã
trực tiếp tận tình hướng dẫn và giúp đỡ em hoàn thành bài khoá luận của mình.
Đồng thời em xin chân thành cảm ơn các thầy cô trong tổ Ứng dụng và các thầy
cô trong khoa Toán - Trường Đại học Sư phạm Hà Nội 2, Ban chủ nhiệm khoa
Toán đã tạo điều kiện cho em hoàn thành tốt bài khoá luận này.
Trong khuôn khổ có hạn của một bài khoá luận, do điều kiện thời gian, do
trình độ có hạn và cũng là lần đầu tiên nghiên cứu khoa học cho nên không tránh
khỏi những hạn chế, thiếu sót nhất định. Vì vậy, em kính mong nhận được những
góp ý của các thầy cô và các bạn.
Em xin chân thành cảm ơn !
Hà Nội, tháng 05 năm 2014
Sinh viên

Phan Thị Hướng


LỜI CAM ĐOAN

Khoá luận này là kết quả của bản thân em trong quá trình học tập và nghiên
cứu. Bên cạnh đó em được sự quan tâm của các thầy cô giáo trong khoa Toán,
đặc biệt là sự hướng dẫn tận tình của TS.Trần Vĩnh Đức.
Trong khi nghiên cứu hoàn thành khoá luận này em đã tham khảo một số tài
liệu đã ghi trong phần tài liệu tham khảo.
Em xin khẳng định kết quả của đề tài “Mối liên hệ giữa đại số, ôtômat và
logic” không có sự trùng lặp với kết quả của các đề tài khác.

Hà Nội, tháng 05 năm 2014
Sinh viên

Phan Thị Hướng


Mục lục
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

Chương 1. Otomat và logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1. Bảng chữ, từ và ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


3

1.2. Một số phép toán trên ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3. Otomat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4. Logic: Tính toán dãy của B¨uchi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4.1. Công thức bậc nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4.2. Công thức monadic bậc hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

¨
Chương 2. Định lý Kleene-Buchi
..................................

17

2.1. Từ otomat đến công thức monadic bậc hai . . . . . . . . . . . . . . . . . . . . .


17

2.2. Từ các công thức đến biểu thức chính quy mở rộng . . . . . . . . . . . . .

18

Chương 3. Ôtômat tối tiểu và vị nhóm cú pháp . . . . . . . . . . . . . . . . . . . . .

28

3.1. Tương đương Myhill-Nerode và ôtômat tối tiểu . . . . . . . . . . . . . . . .

29

3.2. Tính duy nhất và tối tiểu của Amin (L) . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.3. Thuật toán tính toán otomat tối tiểu . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.4. Vị nhóm chuyển của ôtômat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.5. Vị nhóm cú pháp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36


Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42


MỞ ĐẦU

Ngôn ngữ là phương tiện để giao tiếp, sự giao tiếp có thể hiểu là giao tiếp
giữa con người với nhau, giao tiếp giữa người với máy. Ngôn ngữ để con người
có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên, chẳng hạn như tiếng
Anh, tiếng Nga, tiếng Việt,...là các ngôn ngữ tự nhiên. Các quy tắc cú pháp của
ngôn ngữ tự nhiên nói chung là rất phức tạp nhưng các yêu cầu nghiêm ngặt về
mặt ngữ nghĩa thì lại thiếu chặt chẽ, chẳng hạn cùng một từ hay cùng một câu
ta có thể hiểu chúng theo ngữ nghĩa khác nhau tùy theo từng ngữ cảnh cụ thể.
Con người muốn giao tiếp với máy tính tất nhiên cũng thông qua ngôn ngữ.Để
có sự giao tiếp giữa người với máy và giữa máy với nhau, cần phải có một ngôn
ngữ với các quy tắc cú pháp chặt chẽ hơn so với các ngôn ngữ tự nhiên, nói cách
khác, với một từ hay một câu thì ngữ nghĩa của chúng phải là duy nhất mà không
phụ thuộc vào ngữ cảnh. Để xác định các ngôn ngữ như vậy người ta đã sử dụng
ôtômat. Ôtômat dịch nghĩa là máy tự động, được hiểu là các "máy" trừu tượng
có cơ cấu và hoạt động rất đơn giản nhưng có khả năng đoán nhận ngôn ngữ.
Logic là nội dung trung tâm của khoa học máy tính từ khi ngành này được hình
thành.Trong những năm 1950 và 1960, các nhà nghiên cứu dự đoán rằng khi tri
thức của con người có thể được biểu diễn bằng logic và các ký hiệu toán học, sẽ
có khả năng tạo ra một máy tính có khả năng lập luận, hay nói cách khác là trí

tuệ nhân tạo.

Ôtômat và logic sinh ra các ngôn ngữ hình thức, có mối liên hệ chặt chẽ với
nhau, góp phần rất quan trọng trong việc mô tả các dãy tính toán và điều khiển
tự động, được phát sinh trong nhiều ngành khoa học khác nhau, từ hệ thống tính
toán, ngôn ngữ đến sinh học. Khi nghiên cứu với tư cách là đối tượng toán học,
lý thuyết này đề cập đến những vấn đề cơ bản của khoa học máy tính, và các kết
quả nghiên cứu đã có nhiều ứng dụng ngay đối với ngành toán học trừu tượng.
1


8. Cấu trúc khóa luận

Khóa luận gồm:
Chương 1. Ô tômat và logic.
Chương 2.Định lý Kleene − Buchi.
¨
Chương 3.Ôtômat tối tiểu và vị nhóm cú pháp.

2


Chương 1

Otomat và logic
1.1. Bảng chữ, từ và ngôn ngữ
Bảng chữ 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à aabacba 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ụ, |abca| = 4.
Từ không chứa ký hiệu nào gọi là từ rỗng và ký hiệu là ε. Theo định nghĩa
|ε| = 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∗ − {ε}.
Xét hai từ u và v trên bảng chữ A, phép ghép hai từ này là từ uv 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:
|uv| = |u| + |v|
uε = εu = u

3


Một tập con L ⊆ A∗ được gọi là một ngôn ngữ hình thức (hay ngắn gọn là ngôn
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 {ε}.
Ví dụ 1.2. Tập A∗ là ngôn ngữ gồm tất cả các từ trên A, tập A+ là ngôn ngữ
gồm tất cả các từ khác từ rỗng trên A. Còn tập
{ε, 0, 1, 01, 10, 00, 11, 011, 100}
là một ngôn ngữ trên bảng chữ nhị phân {0, 1}.

1.2. Một số phép toán trên ngôn ngữ
Từ các ngôn ngữ có trước, ta có thể thu được một ngôn ngữ mới nhờ áp dụng
các phép toán trên ngôn ngữ. Trước hết nhờ ngôn ngữ là một tập hợp, nên các
phép toán trên tập hợp như hợp, giao, hiệu và phần bù đều có thể áp dụng lên
ngôn ngữ. Ngoài ra, phép ghép có thể có mở rộng tự nhiên cho ngôn ngữ. Ghép

của hai ngôn ngữ K và L trên bảng chữ cái A là ngôn ngữ
KL = {uv | u ∈ K và v ∈ L}
Chúng ta cũng sử dụng ký hiệu lũy thừa cho các ngôn ngữ. Xét n là một số
nguyên dương, và L là một ngôn ngữ, ngôn ngữ Ln được định nghĩa một cách đệ
quy như sau
Ln =



{ε},

nếu n = 0


LLn−1 ,

nếu n > 0

Phép lặp của ngôn ngữ L là ngôn ngữ
L∗ =

Ln .
n≥0

Nếu A và B 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
4


1. ϕ (ε) = ε

2. ∀u, v ∈ A∗ , ϕ (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 = a1 a2 ...an ∈ A∗ thu được bằng cách ghép ảnh của
các chữ, có nghĩa rằng
ϕ(u) = ϕ(a1 )ϕ(a2 ) · · · ϕ(an ).
. 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) = {ϕ (u) | u ∈ 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 ∈ A.
2. Nếu K và L là các ngôn ngữ chính quy thì K ∪ L, KL và L∗ cũng là chính
quy.
Ví dụ 1.3. Xét các ngôn ngữ sau.
• Ngôn ngữ

a∗ (ab)∗ A∗ ∩ A∗ (ba)∗

2 ∗

là chính quy.
• Ngôn ngữ {ε} chỉ gồm từ rỗng là chính quy vì {ε} = 0/ ∗ .
5



• Mọi ngôn ngữ hữu hạn (tức là chỉ gồm hữu hạn từ) là chính quy.

Ví dụ 1.4. Cho a, b ∈ A là các chữ cái phân biệt. Hai ngôn ngữ sau trên A là
chính quy.
1. Ngôn ngữ gồm tất cả các từ không chứa hai chữ a liên tiếp.
2. Ngôn ngữ gồm tất cả các từ chứa từ con ab nhưng không chứa từ con ba.
Chúng ta cũng xem xét các phép toán chính quy mở rộng bao gồm các phép
toán chính quy, và phép giao, lấy phần bù và lấy ảnh đồng cấu. Một ngôn ngữ
được gọi là được chính quy mở rộng 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 lần) phép toán chính quy mở rộng. Lớp của
các ngôn ngữ chính quy mở rộng trên A được ký hiệu là X − RatA∗ . Rõ ràng, tất
cả các ngôn ngữ chính quy đều là chính quy mở rộng.

1.3. Otomat
Một otomat trên bảng chữ cái A là một bộ bốn A = (Q, T, I, F) trong đó Q
là một tập hữu hạn, được gọi là tập trạng thái; T là một tập con của Q × A × Q
được gọi là tập các chuyển; I và F là tập con của Q tương ứng được gọi là tập
trạng thái bắt đầu và tập trạng thái kết thúc. Các trạng thái kết thúc cũng được
gọi là trạng thái chấp nhận.
Đồ thị của một otomat A = (Q, T, I, F) có các đỉnh là các phần tử của tập
a

trạng thái Q và các cạnh có dạng q → q nếu (q, a, q ) là một chuyển, có nghĩa
rằng nếu (q, a, q ) ∈ T . Các trạng thái bắt đầu được thể hiện bởi một mũi tên từ
ngoài đi vào, các trạng thái kết thúc thể hiện bởi mũi tên đi ra ngoài.
Ví dụ 1.5. Cho bảng chữ cái A = {a, b}. Hình 1.1 biểu diễn otomat A =
(Q, T, I, F), ở đó Q = {1, 2, 3}, I = {1}, F = {3} và
T = {(1, a, 1) , (1, b, 1) , (1, a, 2) , (2, b, 3) , (3, a, 3) , (3, b, 3)} .

6



b
1

b
a

2

b

3

a

a

Hình 1.1: Một ôtômat chấp nhận A∗ abA∗

Một đường đi trên otomat A là một dãy cạnh liên tiếp
P = (q0 , a1 , q1 ) (q1 , a2 , q2 ) · · · (qn−1 , an , qn )
cũng được thể hiện bởi dãy mũi tên
a

a

a

P = q0 →1 q1 →2 q2 .... →n qn .

Ta nói P là một đường đi có độ dài n từ q0 đến qn gán nhãn bởi từ từ u =
a1 a2 ....an . 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 1.1, từ a3 ba là nhãn của đúng 4 đường đi: từ 1
đến 1, từ 1 đến 2, từ 1 đến 3 và từ 3 đến 3.
Một đường đi P gọi là thành công nếu trạng thái bắt đầu thuộc I và trạng thái
kết thúc thuộc F. Một từ w được chấp nhận bởi A nếu tồn tại một con đường
thành công trong otomat với nhãn w. Và ngôn ngữ được chấp nhận bởi A là tập
nhãn của mọi đường đi thành công trên A, và ký hiệu bởi L (A).
Ví dụ 1.7. Otomat của hình 1.1 chấp nhận tập mọi từ có ít nhất một lần xuất
hiện của ab, cụ thể A∗ abA∗ , ở đó A = {a, b}.
Các otomat khác nhau có thể chấp nhận cùng ngôn ngữ. Nếu A và B là hai
otomat chấp nhận cùng một ngôn ngữ, tức là L (A) = L (B), chúng ta nói rằng
A và B là tương đương.
Ví dụ 1.8. Ngôn ngữ A∗ abA∗ , được chấp nhận bởi otomat trong hình 1.1, cũng
được chấp nhận bởi otomat trong hình 1.2.
7


b

b
a

b

a

a


Hình 1.2: Một ôtômat khác chấp nhận A∗ abA∗

Một otomat A = (Q, T, I, F) trên bảng chữ cái A được gọi là đủ nếu mỗi trạng
thái q và mỗi chữ cái a, tồn tại ít nhất một chuyển có dạng (q, a, q ).
Có nghĩa rằng, cho mỗi chữ cái a đều có một cạnh gán nhãn bởi a từ mỗi
trạng thái. Một cách tự nhiên, điều này đơn chỉ ra rằng, với mỗi trạng thái q và
mỗi từ w ∈ A∗ , tồn tại ít nhất một con đường dán nhãn w bắt đầu tại q.
Mỗi otomat có thể dễ dàng chuyển đổi thành một otomat đủ tương đương
như sau. Nếu A = (Q, T, I, F) là không đủ, có nghĩa rằng otomata đầy của A là
otomat Acomp = (Q , T , I, F) nhận được từ A bằng cách thêm trạng thái mới z
và T thu được bằng cách thêm vào T các chuyển (z, a, z) với mỗi a ∈ A và các
chuyển (q, a, z) với mỗi q ∈ Q và a ∈ A . Nếu A là đủ, chúng ta có Acomp = A.
Trong mỗi trường hợp trên, Acomp là đủ và L (Acomp ) = L (A).
Chúng ta có thể thấy rằng trên sự làm đầy Acomp 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
8


A là tương đương với một otomat rút gọn, ta viết Atrim là otomat thu được từ A
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à ε − otomat cho
phép chuyển có nhãn ε, tức chuyển có dạng (p, ε, q) với p, q ∈ 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 , (q, a, q”) ∈ 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 nhãn w bắt
đầu tại q.
2. Nếu w ∈ L (A), vậy w là nhãn của đúng một đường đi thành công.
Đặc biệt, ta có thể mô tả các chuyển của otomat đơn định A = (Q, T, I, F)
bởi hàm chuyển: hàm bộ phận δ : Q × A → Q mà ánh xạ mỗi cặp (q, a) ∈ Q × A
đến trạng thái q sao cho(q, a, q ) ∈ T (nếu nó tồn tại). Hàm này được mở rộng tự
nhiên cho tập Q × A∗ : nếu q ∈ Q và w ∈ A∗ , δ (q, w) là trạng thái q thoả mãn tồn
tại một đường đi từ q đến q gán nhãn bởi w trong A (nếu như trạng thái này tồn
tại). Vậy nên otomat đơn định có thể được định nghĩa bởi bộ bốn (Q, δ , i, F) thay
cho (Q, T, {i} , F) tương ứng. Chúng ta có đặc trưng cơ bản sau đây của hàm δ .

9


Mệnh đề 3.2. Cho A = (Q, δ , i, F) là một otomat đơn định. Vậy ta có
δ (q, ε) = q


δ (δ (q, u), a),
δ (q, ua) =


không định nghĩa

nếu cả δ (q, u) và δ (δ (q, u) , a) tồn tại ,
ngược lại;

u ∈ L(A ) nếu và chỉ nếu δ (i, u) ∈ F.
với mỗi trạng thái q, mỗi từ u ∈ A∗ và mỗi chữ cái a ∈ A.
Cho A = (Q, T, I, F) là một otomat. Hàm chuyển tập con của A là hàm
δ : P (Q) × A → P (Q)
được định nghĩa bởi, với mỗi P ⊆ Q, và mỗi a ∈ A
δ (P, a) = {q ∈ Q | ∃p ∈ P, (p, a, q) ∈ T }
Do đó, δ (P, a) là tập hợp các trạng thái của A có thể đạt được bởi một chuyển
gán nhãn a bắt đầu từ một phần tử của P. Otomat tập con của A là Asub =
(P (P) , δ , I, Fsup ) ở đó Fsup = {P ⊆ Q | P ∩ F = φ }.
Do cách xây dựng, otomat Asub là đơn định và đầy đủ, và hàm chuyển tập con
của A là hàm chuyển Asup . Hơn nữa, nếu A có n trạng thái, thì Asup có 2n trạng
thái.
Mệnh đề 3.3. Otomat A và Asub là tương đương.
Chứng minh. 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 ∈ A∗ , giá trị δ (P, w) là tập hợp mọi trạng thái q ∈ 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 A nếu và chỉ nếu ít nhất một trạng thái
kết thúc nằm trong tập δ (I, w), nếu và chỉ nếu δ (I, w) ∈ Fsub nếu và chỉ nếu w
được chấp nhận bởi Asub . Đây là điều phải chứng minh.
10


¨
1.4. Logic: Tính toán dãy của Buchi

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à ∨ 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 (x < y) ∧ Ra x ∧ Rb y.
Công thức này có diễn dịch sau trên một từ u: tồn tại hai số tự nhiên x < y sao
cho, trong u, chữ cái ở vị trí x là a và chữ cái ở vị trí y là b. Do đó công thức
này xác định ngôn ngữ gồm tất cả các từ u thoả mãn công thức trên, đó chính là
ngôn ngữ A∗ aA∗ bA∗ .
1.4.1. Công thức bậc nhất

Ta hình thức hoá cách thể hiện trên của ngôn ngữ.
Cú pháp

Công thức của tính toán dãy B¨uchi thường sử dụng các ký hiệu logic (∧, ∨, ¬),
ký hiệu đồng nhất =, ký hiệu hằng số true, phép lượng hóa ∃ và ∀, các kí hiệu
biến (x, y, z...) và dấu đóng mở ngoặc. Chúng cũng sử dụng ký hiệu: các quan hệ
hai ngôi < và S, và ký hiệu quan hệ một ngôi Ra (cho mỗi chữ cái a ∈ A).
Để thuận lợi chúng ta có thể giả sử rằng các biến được lấy từ tập biến cố định,
đếm được.
Các công thức nguyên thuỷ là các công thức true, x = y, x < y, S(x, y), Ra x,
với x và y là các biến và a ∈ A.
Công thức bậc nhất được định nghĩa như sau:
• Công thức nguyên thuỷ là công thức bậc nhất
• Nếu ϕ và ψ là công thức bậc nhất, vậy thì (¬ϕ) , (ϕ ∧ ψ) và (ϕ ∨ ψ) cũng

là công thức bậc nhất,
11


• Nếu ϕ là công thức bậc nhất và nếu x là một biến, vậy thì (∃xϕ) và (∀xϕ)


cũng là công thức bậc nhất.
Chú ý 1.4.1. Trong các công thức logic, chúng ta sẽ hạn chế sử dụng dấu ngoặc
đơn trong các ký hiệu, ví dụ ∀xRa x thay cho (∀x (Ra x)) .
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 FV (ϕ) của công
thức ϕ như sau:
• Nếu ϕ là nguyên thuỷ, sau đó FV (ϕ) là tập mọi biến các biến số xuất hiện

trongϕ,
• FV (¬ϕ) = FV (ϕ)
• FV (ϕ ∧ ψ) = FV (ϕ ∨ ψ) = FV (ϕ) ∨ FV (ψ)
• FV (∃xϕ) = FV (∀xϕ) = FV (ϕ) \ {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 B¨uchi, các công thức được diễn dịch trong các từ: mỗi từ u
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à u) với miền Dom (u) = (0, ..., n − 1) (Dom (u) = 0/ nếu u = ε).
Dom (u) được xem như tập các vị trí trong từ u (được đánh số từ 0). Ký hiệu <
được diễn dịch trong dom (u) như thứ tự thông thường (như (2 < 4) và ¬ (3 < 2)
). Ký hiệu S được giải thích như các ký hiệu liền sau: Nếu x, y ∈ Dom (u), vậy
S (x, y) nếu và chỉ nếu y = x + 1. Cuối cùng, với mỗi chữ cái a ∈ A, ký hiệu quan
hệ một ngôi Ra được diễn dịch như tập các vị trí trong u mang một ký hiệu a
(đây là một tập con của dom (u)).
Ví dụ 1.10. Nếu u = abbaab, vậy Dom (u) = {0, 1, ..., 5}, Ra = {0, 3, 4} và
Rb = {1, 2, 5}.
12



Một sự đánh giá trên u là một ánh xạ ν từ một tập các giá trị vào miền
Dom (u). Nó sẽ hữu ích để có một ký hiệu cho sự thay đổi nhỏ của một đánh giá.
Nếu ν là một đánh giá và d là một phần tử của Dom (u), ta đặt ν [x → d] là đánh
giá ν xác định bằng cách mở rộng miền của ν bao gồm cả giá trị x và đặt

ν (y) nếu y = x
ν (y) =
 d
nếu y = x
Nếu ϕ là một công thức, u ∈ A∗ và ν là một đánh giá trên u mà miền của nó
bao gồm các biến tự do của ϕ, vậy chúng ta định nghĩa u, ν |= ϕ (và nói rằng
đánh giá ν thỏa mãn ϕ trên u, hoặc tương đương u, ν thỏa mãn ϕ) như sau:
• u, ν |= (x = y) (tương ứng (x < y) , S (x, y) , Ra x) nếu và chỉ nếu ν (x) = ν (y)

(tương ứng ν (x) < ν (y) , S (ν (x) , ν (y)) , Ra ν (x)) trong Dom (u);
• u, ν |= ¬ϕ nếu và chỉ nếu u, ν |= ϕ không đúng;
• u, ν |= (ϕ ∨ ψ) (tương ứng (ϕ ∧ ψ)) nếu và chỉ nếu xảy ra ít nhất một

(tương ứng cả hai) u, ν |= ϕ và u, v |= ψ đúng (tương ứng cùng đúng).
• u, ν |= (∃xϕ) nếu và chỉ nếu tồn tại d ∈ Dom (u) sao cho u, ν [x → d] |= ϕ
• u, ν |= (∀xϕ) nếu và chỉ, với mỗi d ∈ Dom (u) ta có u, ν [x → d] |= ϕ.

Lưu ý rằng giá trị chân lý của u, ν |= ϕ chỉ phụ thuộc vào giá trị được ν gán cho
biến tự do của ϕ. Cụ thể, nếu ϕ là một câu, sau đó đây là một giá trị µ với một
miền rỗng. Chúng ta nói rằng ϕ được thỏa bởi u (hoặc u thỏa ϕ), và chúng ta
viết u |= ϕ cho u, µ |= ϕ. Do đó mỗi câu ϕ xác định một ngôn ngữ L (ϕ) gồm
mọi từ u thoả mãn u |= ϕ. Lưu ý rằng sự giải thích này có ý nghĩa ngay cả khi u
là từ rỗng, thì giá trị µ vẫn được định nghĩa : mọi câu bắt đầu với một lượng từ

phổ dụng đều thỏa mãn bởi ε, và không có câu nào bắt đầu với lượng từ tồn tại
được thỏa mãn bởi ε.
Chú ý 1.4.2. Hai câu ϕ và ψ được nói là tương đương logic nếu chúng thỏa
mãn bởi các cấu trúc giống nhau. Chúng ta sẽ sử dụng một cách tự do kết quả
13


tương đương logic, chảng hạn tương đương logic giữa ϕ ∧ ψ và ¬ (¬ϕ ∨ ¬ψ),
hoặc tương đương logic giữa ∀xϕ và ¬ (∃x¬ϕ). Chúng ta cũng sẽ sử dụng ký
hiệu kéo theo và cùng kéo theo: ϕ → ψ thay cho ¬ϕ ∨ ψ và ϕ ↔ ψ thay cho
(ϕ → ψ) ∧ (ψ → ϕ).
Ví dụ 1.11. Cho ϕ và ψ được cho bởi công thức sau
ϕ = ∃x ((∀y¬ (y < x)) ∧ Ra x)
ψ = ∀x ((∀y¬ (y < x)) → Ra x)
Câu ϕ 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 (ϕ) = aA∗ và L (ψ) = aA∗ ∪ {ε}.
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
FO(<) (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 (Xy), ở đó 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 ϕ là công thức monadic bậc hai và X là một biến tập, thì (∃xϕ) và

∀Xϕ 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ự.
14


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ạ
ν gắn mỗi biến bậc nhất một phần tử của miền Dom (u), và mỗi biến tập, một
tập con của Dom (u).
Nếu ν là một giá trị,X là một biến tập, và R là một tập con của Dom (u), ta
ký hiệu ν [X → R] đánh giáthu được từ ν bởi ánh xạ X đến R.
Với định nghĩa này, chúng ta có thể đưa ra khái niệm đánh giá ν thoả một
công thức ϕ trong một từ (u, v |= ϕ): Chúng ta dùng lại các luật trong phần
trước và thêm một số quy tắc sau:
• u, ν |= (Xy) nếu và chỉ nếu ν (y) ∈ ν (X)
• u, ν |= (∃Xϕ)(tương ứng (∀Xϕ)) nếu và chỉ nếu tồn tại R ⊆ Dom (u) sao

cho (tương ứng cho mỗi R ⊆ Dom (u)), u, v [X → R] |= ϕ.
Lưu ý rằng tập rỗng có thể gán cho một biến tập: Từ rỗng có thể thỏa mãn biến
monadic bậc hai ngay cả khi chúng bắt một lượng từ tồn tại.
Tính toán dãy B¨uchi được mở rộng để chứa công thức monadic bậc hai. Ta
ký hiệu MSO(<) (tương ứng MSO(S)) là các công thức monadic bậc hai không
được sử dụng ký hiệu S (tương ứng <). Tất nhiên, FO(<) và FO(S) tương ứng
là tập con của MSO(<) và MSO(S).
Ví dụ 1.12. Kiểm tra MSO(<) câu sau,
ϕ = ∃X


[∀x (Xx ↔ ((∀y¬ (x < y)) ∨ (∀y¬ (y < x))))
∧ ∀x (Xx → Ra x) ∧ ∃xXx ]

ta thấy rằng các phần tử của X phải được ở các vị trí đầu và cuối của từ mà ϕ
diễn dịch, do đó L (ϕ) = aA∗ ∩ A∗ a. Ngôn ngữ này cũng có thể được mô tả bởi
một câu logic bậc nhất, có nghĩa rằng, công thức này tương đương đến một công
thức bậc nhất.

15


Ví dụ 1.13. Kiểm tra MSO(<) của câu sau,
ϕ = ∃X

(((∀x∀y ((x < y)) ∧ (∀z¬ ((x < z) ∧ (z < y)))) → (Xx ↔ ¬Xy))
∧ (∀x (∀y¬ (y < x)) → Xx)
∧ (∀x (∀y¬ (x < y)) → ¬Xx))

Công thức ϕ khẳng định rằng có tồn tại một tập X gồm các vị trí trong từ sao
cho một vị 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 (ϕ) 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 FO(<): S(x, y) tương đương logic
với công thức sau:
(x < y) ∧ ∀z ((x < z) → ((y = z) ∨ (y < z)))
Ngược lại, quan hệ thứ tự < là có thể được biểu thị trong MSO(S): Công thức
x < y tương đương logic với công thức:
∃X (Xy ∧ ¬Xx ∧ [∀z∀t ((Xz ∧ S (z,t)) → Xt)])
Sau đó MSO(<) và MSO(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 FO(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.

16


Chương 2

¨
Định lý Kleene-Buchi
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¨uchi.
Đị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, δ , F) là một otomat đơn định. Ý tưởng ở đây là gắn mỗi mỗi
trạng thái q ∈ Q với một biến bậc hai Xq , để mã hoá tập hợp các vị trí mà đường
đi cho trước đi qua trạng thái q. Giải thích chi của tập Xq như sau:
• Các tập Xq tạo thành một phân hoạch tập mọi vị trí (tại mỗi điểm, otomat


chỉ ở đúng một trạng thái);
• Nếu một đường đi qua trạng thái q tại thời điểm x, qua trạng thái q tại thời

điểm x + 1 và nếu chữ cái ở vị trí x + 1 là một a, vậy thì δ (q, a) = q ;
17


Giải thích này dẫn đến công thức sau đây. Để tiện, đặt Q là tập {q0 , q1 , ....., qn },
với trạng thái bắt đầu i = q0 . Chúng ta cũng sử dụng ký hiệu min và max để chỉ
vị trí đầu tiên và cuối cùng: ta có thể biểu diễn vị trí này như công thức trong
FO(S). Ví dụ, Ra min bởi công thức ∀x (∀y¬S (y, x) → Ra x); và X max bởi công
thức ∀x (∀y¬S (x, y) → Xx).
∃Xq0

∃Xq1

···

∃Xqn

¬∃x Xq x ∧ Xq x ∧ ∀x Xq x
q

q=q

∧∀x∀y S (x, y) →
q∈Q,a∈A

∧
a∈A


Xq x ∧ Ra y ∧ Xδ (q,a) y

Ra min → Xδ (q0 ,a) min ∧

Xq max
q∈F

Câu này luôn thoả mãn từ rỗng, và vậy thì ngôn ngữ được định nghĩa trùng với
L (A) trong A+ . Nếu q0 ∈ F, nó định nghĩa chính xác L (A). Nhưng nếu q0 ∈
/ F,
chúng ta phải xem xét hội câu này các câu này với câu ∃x true.
Đây là một câu trong MSO(S, <) nhưng như chúng ta biết, nó là tương đương
logic với MSO(<). 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 MSO(<) 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.

18


Các bảng chữ cái phụ B p,q

Cho p, q ≥ 0 và cho B p,q = A × {0, 1} p × {0, 1}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
(u0 , u1 , ..., u p , u p+1 , ..., u p+q )
ở đó u0 ∈ A∗ , u1 , ..., u p , u p+1 , ..., u p+q ∈ {0, 1}∗ và mọi ui đề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
u1 , ..., u p chứa chính xác một sự xuất hiện của 1. Do đó mỗi thành phần này
xác định đúng một vị trí trong từ u0 , và mỗi thành phần u p+1 , ..., u p+q xác định
một tập vị trí trong u0 .
Ví dụ 2.1. Nếu A = {a, b}, dưới đây là một từ trong K2,1 :
u0

a b a a b a b

u1

0 0 0 0 1 0 0

u2

0 0 1 0 0 0 0

u3

0 1 1 0 0 1 1

Các thành phần u1 và u2 xác định các vị trí 4 và 2, tương ứng, và thành phần u3
xác định tập {1, 2, 5, 6}.
Các ngôn ngữ K p,q là chính quy mở rộng. Thật vậy, cho 1 ≤ i ≤ p, xét Ci là
tập hợp các phần tử (b0 , b1 , ..., b p+q ) ∈ B p,q sao cho bi = 1. Vậy K p,q là tập hợp
các phần tử trong B+

p,q chứa ít nhất một chữ cái trong mỗi Ci :
(B p,q \Ci )∗ Ci (B p,q \Ci )∗

K p,q = {ε} ∪
1≤i≤p

= B∗p,q \

B∗p,qCi B∗p,qCi B∗p,q
1≤i≤p

19


Ngôn ngữ gắn với công thức

Bây giờ xét
ϕ (x1 , ..., xr , X1 , ..., Xs )
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à x1 , ....., xr
(tương ứng là X1 , X2 , ...., Xs ), với r ≤ p và s ≤ q.
Chúng ta diễn dịch.
• Ra như Ra = {i ∈ Dom (u) | u0 (i) = a};
• xi như vị trí duy nhất của 1 trong ui (nếu ui = ε);
• X j như tập vị trí của 1 trong u p+ j .

Để ý rằng nếu p = q = 0, thì ϕ là một câu và đây là ký hiệu thông thường trong
diễn dịch.
Hình thức hơn, xét (u0 , u1 , ..., u p+q ) là một từ không rỗng trong K p,q . Cho ni
là vị trí duy nhất của 1 trong từ ui và cho N j là tập các vị trí của 1 trong từ u p+ j .
Chúng ta nói rằng u = (u0 , u1 , ..., u p+q ) ∈ K p,q thỏa mãn ϕ nếu u0 , ν thỏa mãn

ϕ ở đó ν là đánh giá định nghĩa bởi
v (xi ) = ni

với 1 ≤ i ≤ r

và

ν (X j ) = N j

với 1 ≤ j ≤ s

Chúng ta cũng nói rằng từ rỗng ( trong K p,q ) thỏa mãn ϕ nếu ε |= ϕ. Chúng đặt
L p,q (ϕ) = u ∈ K p,q | u thỏa mãn ϕ
Do đó mỗi công thức ϕ định nghĩa một tập con của K p,q , và do đó nó là ngôn
ngữ trong B+
p,q .
Ví dụ 2.2. Xét
ϕ = ∃x (x < y ∧ Ra y) .
Vậy thì FV (ϕ) = {y}. Và L1,0 (ϕ) là tập các cặp từ (u0 , u1 ) thoả mãn u0 ∈
A∗ , u1 ∈ {0, 1}∗ , u0 và u1 có độ dài giống nhau, u1 chỉ có một 1 nhưng ở vị trí
đầu tiên, và u0 có một a ở vị trí này.
20


Xét
ϕ = ∀x ((Xx ∧ x < y ∧ Rb y) → Ra x) .
Vậy thì L1,1 (ϕ) là tập các bộ ba từ (u0 , u1 , u2 ) với u0 ∈ A∗ , u1 , u2 ∈ {0, 1}∗ , cả
ba từ này có cùng độ dài giống nhau, và không có độ dài nào bằng 0, hoặc u1 có
1 thoả mãn:
Cho n là vị trí của 1 trong u1 . Nếu u0 có b ở vị trí n, vậy thì u0 có một

a trong mỗi vị trí trước n mà ở đó u2 có một 1. Nếu u0 không có một b
trong vị trí n, vậy thì không có ràng buộc nào.
Ngôn ngữ định nghĩa bởi MSO(<) là chính quy mở rộng

Đầu tiên chúng ta xem xét các ngôn ngữ gắn với một công thức nguyên tử .
Xét 1 ≤ i, j ≤ p + q và xét a ∈ A. Đặt
C j,a = b ∈ B p,q | b j = 1 và b0 = a
Ci, j = b ∈ B p,q | bi = b j = 1
Ci = b ∈ B p,q | bi = 1
Vậy ta có
L p,q (Ra xi ) = K p,q ∩ B∗p,qCi,a B∗p,q
L p,q (xi = x j ) = K p,q ∩ B∗p,qCi, j B∗p,q
L p,q (xi < x j ) = K p,q ∩ B∗p,qCi B∗p,qC j B∗p,q
L p,q (Xi x j ) = K p,q ∩ B∗p,qCi+p, j B∗p,q
Do đó, các ngôn ngữ định nghĩa bởi các công thức nguyên tử, cụ thể L p,q (Ra xi ),
L p,q (xi = x j ), L p,q (xi < x j ), và L p,q (Xi x j ) là chính quy mở rộng.
Bây giờ cho ϕ và ψ là các công thức và chúng ta giả sử rằng L p,q (ϕ) và

21