PHỤ LỤC
CHƯƠNG I
Automat đơn định (Deterministic Finite Automat –
DFA) Tr 1
I.1. Mô tả không hình thức Tr 1
I.2. Mô tả hình thức Tr 2
I.3. DFA xử lý xâu như thế nào Tr
2
I.4. Các cách biểu diễn đơn giản hơn của DFA Tr
4
a. Biểu đồ dịch chuyển Tr 4
b. Bảng dịch chuyển Tr 5
I.5. Hàm dịch chuyển mở rộng Tr
5
I.6. Ngôn ngữ được thừa nhận bởi DFA Tr
7
CHƯƠNG II
Sự tương đương của các Automat DFA Tr 9
II.1. Sự tương đương của các trạng thái Tr
9
II.2. Sự tương đương của các DFA Tr 11
a. Dự vào bảng đánh dấu sự tương đương các trạng
thái Tr 11
b. Dựa vào tính đóng dưới phép giao Tr 12
II.3. Cài đặt Tr
15
a.Cài đặt dựa theo trạng thái tương đương Tr 16
b. Dựa vào tính đóng của phép giao 2 DFA Tr 22
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
CHƯƠNG I
AUTOMAT ĐƠN ĐỊNH

, F), trong đó:
. Q là tập hợp hữu hạn các trạng thái.
. Σ là bộ chữ cái nhập hữu hạn.
. δ là hàm chuyển ánh xạ từ Q × Σ → Q, tức là δ(q, a) là một trạng thái được
cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a thì nó chuyển sang trạng
thái q’.
. q
0
∈ Q là trạng thái bắt đầu
. F ⊆ Q là tập các trạng thái kết thúc.
I.3. DFA xử lý xâu như thế nào
Giả sử w = a
0
a
1
a
n
là xâu vào. DFA sẽ bắt đầu với trạng thái q
0
, nó sẽ thực
hiện dịch chuyển δ(q
0
, a
1
) giả sử cho q
1
. DFA bây giờ ở trạng thái q
1
và kí hiệu tiếp
theo sẽ đọc a

, ở trạng thái này, DFA có thể tiếp tục đọc bất kì kí hiệu nào.
Như thế δ(q
2
, 0) = δ(q
2
, 1) = q
2
.
Trường hơp (2) sẽ tương ứng với trạng thái đầu q0, khi ở trạng thái này DFA
có thể tiếp tục đọc kí tự cho đến khi gặp kí tự 0 thì chuyển sang trạng thái khác.
Như thế δ(q
0
, 1) = q
0
, δ(q
0
, 0) = q
1
.
Trường hợp (3) sẽ tương ứng với trạng thái q
1
, khi đã đọc trước đó ít nhất một
kí tự 0, nhưng chưa bao giờ đọc xâu 01.Ở trạng thái q
1
thì DFA có thể tiếp tục đọc
kí tự 0 cho đến khi gặp kí tự 1, thì chuyển sang trạng thái thừa nhận q
2
. Như thế
δ(q
1

chuyển.
a. Biểu đồ dịch chuyển
Mỗi trạng thái trong Q là một nút.
Với mỗi trạng thái q ∈ Q và mỗi kí hiệu a ∈ Σ, có δ(q, a) = p ∈ Q. Như thế,
biểu đồ dịch chuyển có một cung đi từ nút p đến q mang nhãn a, nếu có nhiều kí
hiệu tạo ta dịch chuyển từ q đến p thì chỉ cần biểu diễn một cung mang nhãn là
danh sách các kí hiệu đó.
Có một mũi tên đi vào nút q0 để kí hiệu trạng thái đầu.
Các trạng thái kết thúc F là các nút được biểu diễn bởi hai vòng tròn.
Các trạng thái không thuộc F là các nút được biểu diễn bởi chỉ một vòng tròn
Ví dụ:
Nguyễn Thái Thành-Tin Học 2
Trang 5
q := q
0
;
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo}
While c <> $ do
begin
q := δ(q, c);
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
DFA biểu diễn ngôn ngữ trong Ví dụ
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 (
*

Ví dụ: Xây dựng DFA thừa nhận ngôn ngữ
L = {w / w chỉ chứa các kí hiệu 0, 1 và luôn kết thúc bởi kí hiệu 1}
DFA phải phân biệt hai khả năng:
Khi nó đọc kí hiệu 1, thì ngay sau đó có thể kết thúc.
Khi nó đọc kí hiệu 0 thì ngay sau đó không được kết thúc, mà phải đọc tiếp
các kí hiệu khác cho đến khi gặp kí hiệu 1. Như thế, DFA sẽ có ít nhất hai trạng
thái tương ứng với hai khả năng trên.
Ta xây dựng DFA như sau:
M = ({q
0
, q
1
}, {0, 1}, δ, q
0
, {q
1
})
Trong đó, hàm δ như sau:
DFA cho Ví dụ
Hay chúng ta có thể biểu diễn hàm δ bởi bảng dịch chuyển như sau:
Nguyễn Thái Thành-Tin Học 2
Trang 7
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
δ 0 1
q
0
q
0
q
1

δ
*
(q
0
, 10) = δ(δ
*
(q
0
, 1), 0) = δ

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

(q
0
, 1) = q
1
δ
*

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

(q
0
, 1) = q
1
Như vậy, xâu vào w = 101101 được thừa nhận bởi DFA
Chúng ta có thể biểu diễn quá trình đoán nhận đơn giản hơn như sau:
q
0
- 101101  q
1
- 01101  q
0
-1101  q
1
-101  q
1
-01 q
0
-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

m
/ n, m > 0} là ngôn ngữ chính
quy.
Để chứng minh một ngôn ngữ là chính quy, ta chỉ ra rằng tồn tại DFA thừa
nhận ngôn ngữ đó. Thật vậy L được thừa nhận bởi DFA sau:
Nguyễn Thái Thành-Tin Học 2
Trang 9
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
CHƯƠNG II
SỰ TƯƠNG ĐƯƠNG CỦA CÁC AUTOMAT DFA
II.1. Sự tương đương của các trạng thái.
Mục đích của chúng ta là xác định xem hai trạng thái khác nhau p và q có thể
thay thế bởi một trạng thái duy nhất mà có chức năng như p và q.
Chúng ta nói rằng, hai trạng thái p và q là tương đương nếu: với mọi xâu w,
δ
*
(p, w) cho kết quả là trạng thái kết thúc và δ
*
(q, w) cho kết quả cũng là trạng
thái kết thúc hoặc δ
*
(p, w) cho kết quả là trạng thái không kết thúc và δ
*
(q, w) cho
kết quả cũng là trạng thái không kết thúc.
Lưu ý, chúng ta không yêu cầu δ
*
(p, w) và δ
*
(q, w) cho cùng trạng thái mà chỉ

*
(r, w) và δ
*
(s, w), nghĩa
là {p, q} cũng là cặp trạng thái phân biệt bởi xâu aw.
Ví dụ: Xây dựng bảng đánh dấu của DFA trong hình vẽ
Trong bảng đánh dấu các trạng thái phân biệt, các cặp trạng thái phân biệt
được đánh dấu X, các cặp trạng thái tương đương được để trống, các ô bôi đen
không được sử dụng. Ban đầu, không có cặp nào bị đánh dấu. Chúng ta thực hiện
việc đánh dấu theo thuật toán đã trình bày ở trên.
Trước hết, các cặp trạng thái gồm có một trạng kết thúc và một trạng thái
không kết thúc được đánh dấu. Thực hiện bước 2 của thuật toán, chúng ta không
tìm thấy thêm cặp trạng thái phân biệt nào nữa
Bảng đánh dấu các cặp trạng thái phân biệt cho Ví dụ
Nguyễn Thái Thành-Tin Học 2
Trang 11
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
II.2. Sự tương đương của các DFA.
Ví dụ: Xét hai DFA, hai DFA này cùng đoán nhận ngôn ngữ gồm các xâu trên
bảng chữ {0, 1} kết thúc bởi kí hiệu 0.
a. Dựa vào bảng đánh dấu sự tương đương các trạng thái
Chúng ta dễ dàng xác định được sự tương đương của hai DFA. Thật vậy, giả
sử có hai DFA M
1
và M
2
. Xét DFA mới là hợp của hai DFA M
1
và M
2

cũng là ngôn ngữ
chính quy
Chứng minh: Chúng ta xây dựng trực tiếp DFA thừa nhận ngôn ngữ L
1
∩ L
2
từ các DFA thừa nhận L
1
và L
2
.
Giả sử M
1
= (Q
1
, Σ
1
, δ
1
, q
01
, F
1
) và M
2
= (Q
2
, Σ
2
, δ

thời cả hai DFA M
1
và M
2
cùng đoán nhận xâu vào. Như vậy, M được xây dựng
như sau:
M=(Q
1
× Q
2
, Σ
1
∪ Σ
2
, δ, (q
01
, q
02
), F
1
× F
2
)
Trong đó, δ((p, q), a) = (δ1(p, a), δ2(q, a)), với p ∈ Q1, q∈ Q2, a ∈ Σ1∪ Σ2.
Dễ dàng nhận thấy rằng L(M) = L(M1) ∩ L(M2).
Thật vậy, δ
*
((q
01
, q

, nghĩa là M chỉ chấp nhận w khi
M
1
chấp nhận w và M
2
chấp nhận w. Vậy chấp nhận L(M
1
) ∪ L(M
2
)
Ví dụ: Cho L
1
là ngôn ngữ chính quy có chứa ít nhất một kí hiệu 0 được thừa
nhận bởi DFA M
1
(a) và L
2
là ngôn ngữ chính quy có ít nhất một kí hiệu 1 được
thừa nhận bởi DFA M
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
.
Nguyễn Thái Thành-Tin Học 2
Trang 13
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
DFA giao của hai DFA

Automat DFA rỗng: Nếu không tồn tại một đương đi từ trạng thái đầu đến
một trong các trạng thái cuối thì là rỗng, ngược lại thì không rỗng.
Áp dụng cho Ví dụ
Nguyễn Thái Thành-Tin Học 2
Trang 14
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
DFA biểu diễn
1
L
DFA biểu diễn
2
L
DFA biểu diễn
2
L
Nguyễn Thái Thành-Tin Học 2
Trang 15
Môn học Automat và NNHT Đề 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

int n2;int d2[20][20];
void nhapmt1(int d1[][20], int n1)
{
for(int i=0;i<n1;i++)
for(int j=0;j<3;j++)
{
cout<<"\n d1["<<i<<", "<<j<<"]=";
cin>>d1[i][j];
}
}
void inmt1(int d1[][20], int n1)
{
for(int i=0;i<n1;i++)
Nguyễn Thái Thành-Tin Học 2
Trang 17
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
{ for(int j=0;j<3;j++)
cout<<setw(4)<<d1[i][j];
cout<<endl;
}
}
Nguyễn Thái Thành-Tin Học 2
Trang 18
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
void nhapmt2(int d2[][20], int n2)
{
for(int i=0;i<n2;i++)
for(int j=0;j<3;j++)
{
cout<<"\n d2["<<i<<", "<<j<<"]=";

cout<<"\n nhap trang thai dau cua DFA 1:";
cin>>td1;
cout<<"\n nhap trang thai dau cua DFA 2:";
cin>>td2;
*
/
if(ss2dong(d1, d2, 0, 0)==1)
return 1;
else
return 0;
}
// tim vi tri trang thai cuoi cua DFA 1
int timttc1(int d1[][20], int n1)
{ int vt1=-1;
for(int i=0;i<n1;i++)
{
if(d1[i][0]==0)
vt1=i;
}
return vt1;
}
// tim vi tri trang thai cuoi cua DFA 2
int timttc2(int d2[][20], int n2)
{
int vt2=-1;
for(int i=0;i<n2;i++)
{
Nguyễn Thái Thành-Tin Học 2
Trang 20
Môn học Automat và NNHT Đề tài: Hai DFA tương đương

Môn học Automat và NNHT Đề tài: Hai DFA tương đương
else
return 0;
}
void DFAtd(int d1[][20], int d2[][20], int n1, int n2)
{
if(ss2ttd(d1, d2)==0)
{
cout<<"\n hai DFA khong tuong duong";
//cout<<endl;
}
if(ss2ttc(d1, d2, n1, n2)==0)
{
cout<<"\n hai DFA khong tuong duong";
//cout<<endl;
}
if(ss2dongbk(d1, d2, n1, n2)==0)
{
cout<<"\n hai DFA khong tuong duong";
//cout<<endl;
}
if(ss2dongbk(d2, d1, n2, n1)==0)
{
cout<<"\n hai DFA khong tuong duong";
//cout<<endl;
}
else
cout<<"\n hai DFA tuong duong";
}
Nguyễn Thái Thành-Tin Học 2

#include<iomanip.h>
#include<math.h>
#include<fstream.h>
int n1;int d1[20][20];
int n2;int d2[20][20];
void nhapmt1(int d1[][20], int n1)
{
for(int i=0;i<n1;i++)
for(int j=0;j<3;j++)
{
cout<<"\n d1["<<i<<", "<<j<<"]=";
cin>>d1[i][j];
}
}
void inmt1(int d1[][20], int n1)
{
for(int i=0;i<n1;i++)
{
for(int j=0;j<3;j++)
cout<<setw(4)<<d1[i][j];
cout<<endl;
}
Nguyễn Thái Thành-Tin Học 2
Trang 24
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
}
void nhapmt2(int d2[][20], int n2)
{
for(int i=0;i<n2;i++)
for(int j=0;j<3;j++)