MỤC LỤC
Môn học Automata Đề tài: Hai DFA tương đương
Chương I.
AUTOMAT ĐƠN ĐỊNH
(Deterministic Finite Automat – DFA)
I.1. Mô tả không hình thức
Automat hữu hạn là một cái máy đoán nhận xâu. Nó bao gồm các bộ phận
sau:
- Một băng vào được chia thành ô, dùng để ghi xâu vào, mỗi kí hiệu của
xâu vào thuộc bảng chữ Σ được ghi trên một ô
- Một đầu đọc, mỗi thời điểm đọc (trỏ) đến một ô trên băng vào
- Một bộ điều khiển Q, gồm một số hữu hạn các trạng thái, tại mỗi thời
điểm nó có một trạng thái
Hoạt động của Automat được thực hiện như sau: Automat hoạt động theo
từng bước. Mỗi bước như sau: tùy theo trạng thái hiện thời của bộ điều khiển
và kí hiệu mà đầu đọc đang đọc, mà Automat chuyển sang một trạng thái mới,
đồng thời đầu đọc dịch chuyển sang phải một ô.
Quy luật chuyển trạng thái của Automat hữu hạn đơn định được mô tả bởi
một hàm, được gọi là hàm dich chuyển như sau:
Trang 2
2
Môn học Automata Đề tài: Hai DFA tương đương
Trong Q, có một trạng thái đầu, thường kí hiệu qo và một tập hợp các
trạng thái cuối / thừa nhận, thường kí hiệu F (F ⊆ Q).
Ta nói Automat thừa nhận xâu vào w nếu sau khi xuất phát từ trạng thái
đầu qo và đầu đọc chỉ vào kí hiệu bên trái nhất của xâu w, sau một số bước
dịch chuyển hữu hạn, Automat đọc xong xâu w và rơi vào một trong các trạng
thái cuối thuộc F.
Tập hợp tất cả các xâu đoán nhận bởi Automat hợp thành ngôn ngữ được
nhận bởi Automat đó.
I.2. Mô tả hình thức

1
và kí hiệu
tiếp theo sẽ đọc a
2
, nó thưc hiện dịch chuyển δ(q
1
, a
2
) giả sử cho q
2
. Nó cứ tiếp
tục như thế, cho đến khi đọc an thì sẽ chuyển sang trạng thái qn nào đó, nếu q
n
thuộc tập F thì DFA thừa nhận xâu vào w, ngược lại thì xâu vào sẽ không được
thừa nhận.
Trang 3
3
Môn học Automata Đề tài: Hai DFA tương đương
Ví dụ: Xây dựng DFA thừa nhận các xâu gồm các kí hiệu 0, 1 và chứa ít
nhất một lần xâu 01, nghĩa là chúng ta có thể mô tả ngôn ngữ L này như sau:
L = { x01y / x và y gồm các kí tự 0 và 1 bất kì }
Để xây dựng DFA thừa nhận L, DFA M cần phải ghi nhớ các khả năng
sau:
DFA đã đọc xâu 01, như thế sau đó nó có thể thừa nhận xâu vào.
DFA chưa bao giờ đọc kí tự 0, nhưng nó đã đọc ít nhất kí tự 1, trong
trường hợp này nó có thể tiếp tục đọc các kí tự 1 cho đến khi nào đó một kí tự 0
đầu tiên, thì nó có thể sau đó đọc một kí tự 1 đi liền sau.
DFA chưa đọc xâu 01, nhưng ngay trước đó ít nhất một kí tự 0, như thế nó
có thể tiếp tục đọc kí tự 0 cho đến khi gặp một kí tự 1 thì có thể chuyển sang
thừa nhận xâu vào.

2
.
Như thế δ(q
1
, 0) = δ(q
1
, 1) =q
2
.
Vậy cuối cùng chúng ta có DFA như sau:
M=({q
0
, q
1
, q
2
}, {0, 1}, δ, q
0
, {q
2
})
Với δ được định nghĩa như trên.
Trang 4
4
Môn học Automata Đề tài: Hai DFA tương đương
Giải thuật mô phỏng hoạt động của một DFA
Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ L(M) đoán
nhận bởi automata M.
Input: chuỗi nhập x$
Output: câu trả lời ‘YES’ hoặc ‘NO’

b. Bảng dịch chuyển
Bảng dịch chuyển cho một DFA là một quy ước biểu diễn dạng bảng của
hàm, mà ở đây là dịch chuyển với hai tham số: các trạng thái và các kí hiệu
vào. Trạng thái đầu được đánh dấu bởi dấu , các trạng thái cuối sẽ được đánh
các dấu
*
.
Bảng dịch chuyển của DFA xây dựng trong Ví dụ
I.5. Hàm dịch chuyển mở rộng
Một cách không hình thức chúng ta có thể nhận thấy rằng, một DFA định
nghĩa ngôn ngữ gồm các xâu là kết quả của quá trình dịch chuyển từ trạng thái
đầu đến một trong các trạng thái thừa nhận. Để xác định ngôn ngữ được thừa
nhận bởi một DFA, chúng ta sẽ định nghĩa hàm dịch chuyển mở rộng. Hàm
dịch chuyển mở rộng, kí hiệu là δ
*
, sẽ nhận tham số là trạng thái q và xâu w và
trả về trạng thái p. Nghĩa là DFA đang ở trạng thái q, sau khi xử lý xâu w thì
DFA đạt đến trạng thái p.
Trang 6
6
Môn học Automata Đề tài: Hai DFA tương đương
Định nghĩa: Hàm dịch chuyển mở rộng được định nghĩa đệ quy trên độ dài
của xâu như sau:
δ
*
(q, ε) =q, với mọi trạng thái q, nếu DFA không đọc kí hiệu vào nào sẽ ở
lại trạng thái đó.
δ
*
(q, w)= δ (δ

q
0
q
0
q
1

*
q
1
q
0
q
1
Sử dụng hàm dịch chuyển mở rộng để đoán nhận xâu w = 101101 của
ngôn ngữ L.
δ
*
(q
0
, ε) = q
0
δ
*
(q
0
, 1) = δ

(δ
*

(q
0
, 1) = q
1
δ
*
(q
0
, 1011) = δ(δ
*
(q
0
, 101), 1) = δ

(q
1
, 1) = q
1
δ
*
(q
0
, 10110) = δ(δ
*
(q
0
, 1011), 0) = δ

(q
1

-1 q
1
∈ F
I.6. Ngôn ngữ được thừa nhận bởi DFA
Định nghĩa: Cho DFA M = (Q, Σ, δ, q
0
, F), ngôn ngữ được thừa nhận
bởi M, được kí hiệu là L(M), được định nghĩa như sau:
L(M) = { w ∈ Σ
*
/ δ
*
(q
0
, w) = q
f
, q
f
∈ F}
Nghĩa là, ngôn ngữ L(M) gồm các xâu w sao cho M xuất phát từ trạng thái
đầu q0, sau khi đọc hết xâu w thì đạt đến một trong các trạng thái q
f
thuộc F.
Trang 8
8
Môn học Automata Đề tài: Hai DFA tương đương
Định nghĩa: Cho DFA M, một ngôn ngữ L = L(M) được gọi là ngôn ngữ
chính quy (regular language). Hay nói cách khác, ngôn ngữ được thừa nhận bởi
một Automat hữu hạn đơn định là ngôn ngữ chính quy.
Ví dụ: Xây dựng Automat thừa nhận ngôn ngữ L gồm các xâu trên bảng

*
(p, w) và δ
*
(q, w) cho cùng trạng thái mà
chỉ cho kết quả cùng trạng thái kết thúc hoặc không kết thúc.
Ngược lại, hai trạng thái không tương đương được gọi là phân biệt. Nghĩa
là trạng thái p phân biệt với trạng thái q, nếu tồn tại ít nhất một xâu w sao cho
một trong hai dịch chuyển δ
*
(p, w) và δ
*
(q, w) cho trạng thái kết thúc và dịch
chuyển còn lại cho trạng thái không kết thúc.
Để xác định sự tương đương của các trạng thái, chúng ta sử dụng thuật
toán xây dựng bảng đánh dấu như sau:
Nếu p là trạng thái không kết thúc và q là trạng thái kết thúc thì {p, q} là
cặp trạng thái phân biệt.
Cho p và q là các trạng thái sao cho với kí hiệu vào a, r = δ (p, a) và
s= δ (q, a) là cặp trạng thái phân biệt. Khi đó {p, q} cũng là cặp trạng thái
phân biệt. Thật vậy, bởi vì {r, s} là cặp trạng thái phân biệt, nên tồn tại xâu w
phân biệt r và s, nghĩa là chỉ có một trong hai dịch chuyển δ
*
(r, w) và δ
*
(s, w)
cho kết quả là trang thái kết thúc, còn một dịch chuyển cho kết quả là trạng thái
Trang 10
10
Môn học Automata Đề tài: Hai DFA tương đương
không kết thúc. Khi đó, δ

2
. Xét DFA mới là hợp của hai DFA M
1
và M
2
.
Khi đó, DFA này có hai trạng thái đầu. Tuy nhiên, nếu DFA M
1
và M
2
là
tương đương thì cặp trạng thái đầu phải là cặp trạng thái tương đương. Ngược
lại, nếu cặp trạng thái đầu là cặp trạng thái phân biêt thì M
1
và M
2
là không
tương đương.
Áp dụng thuật toán
Trang 12
12
Môn học Automata Đề tài: Hai DFA tương đương
Chúng ta coi hai DFA như là một DFA với các trạng thái là A, B, C, D và
E. Bây giờ xây dựng bảng đánh dấu các trạng thái phân biệt của DFA này.
A và C là cặp trạng thái tương đương, vậy hai DFA là tương đương. Tức
là cùng thừa nhận một ngôn ngữ.
b. Dựa vào tính đóng dưới phép giao
Định lý: Nếu L
1
và L

2
= (Q
2
, Σ
2
, δ
2
, q
02
, F
2
) là các DFA
thừa nhận tương ứng L
1
và L
2
. Chúng ta sẽ xây dựng DFA M bắt chước thực
hiện đồng thời M
1
và M
2
. Mỗi trạng thái của M sẽ là một cặp trạng thái: một
trạng thái của M
1
và một trạng thái của M
2
. Bảng chữ của M sẽ là hợp của các
bảng chữ của M
1
và M

Trong đó, δ((p, q), a) = (δ1(p, a), δ2(q, a)), với p ∈ Q1, q∈ Q2, a ∈ Σ1∪
Σ2.
Trang 13
13
Môn học Automata Đề tài: Hai DFA tương đương
Dễ dàng nhận thấy rằng L(M) = L(M1) ∩ L(M2).
Thật vậy, δ
*
((q
01
, q
02
), w) = (δ
1

*
(q
01
, w), δ
2

*
(q
02
, w)), như thế M chỉ chấp
nhận w khi δ
1

*
(q

2
(b). Chúng ta chỉ ra DFA M (c) thừa nhận ngôn
ngữ giao của L
1
và L
2
.
Trang 14
14
Môn học Automata Đề tài: Hai DFA tương đương
DFA giao của hai DFA
Chúng ta dễ dàng nhận thấy rằng, DFA thừa nhận ngôn ngữ gồm it nhất
một kí hiệu 0 và ít nhất một kí hiệu 1.

*
Áp dụng thuật toán
Trang 15
15
Môn học Automata Đề tài: Hai DFA tương đương
Để chứng minh hai DFA
1
L
và
2
L
tương đương thì ta chứng minh như
sau:
1
L
=

DFA biểu diễn
2
L
Trang 18
18
Môn học Automata Đề tài: Hai DFA tương đương
DFA biểu diễn
1
L
∩
2
L
= L(M)
Ta thấy L(M) là một Automat rỗng vì không tồn tại đương đi nào từ (A,
C) đến (A, E).
Tương tự ta có L(M)=
1
L
∩
2
L
cũng rỗng.
Suy ra hai DFA
1
L
,
2
L
tương đương.
II.3. Cài đặt