MỤC LỤC
MỤC LỤC 1
I. ĐẶT VẤN ĐỀ 2
II. CƠ SỞ LÝ THUYẾT 3
II.1. Định nghĩa DFA 3
II.1.1. Mô tả không hình thức 3
II.1.2. Mô tả hình thức: 4
II.1.3. DFA xử lý xâu như thế nào? 4
II.1.4. Các cách biểu diễn đơn giản hơn của DFA 5
a.Bằng đồ thị có hướng: 5
b.Bảng dịch chuyển 5
Bảng chuyển là bảng có kích cỡ |Q| × |Σ|, trong đó dòng i cột j của bảng là δ(qi, aj) hoặc
bỏ trống 5
II.2. SỰ TƯƠNG ĐƯƠNG CỦA CÁC AUTOMAT DFA 6
II.2.1. Sự tương đương của các trạng thái: 6
II.2.2. Sự tương đương của các DFA 7
a. Dựa vào bảng đánh dấu sự tương đương các trạng thái 8
b.Dựa vào tính đóng dưới phép giao 8
III. CẤU TRÚC CHƯƠNG TRÌNH 12
III.1. Cấu trúc 12
III.1.1. Cài đặt dựa theo trạng thái tương đương 13
III.1.2. Dựa vào tính đóng của phép giao 2 DFA 13
III.2. Sơ đồ khối các bước giải quyết công việc: 13
III.2.1.Cài đặt dựa theo trạng thái tương đương 13
III.2.2. Dựa vào tính đóng của phép giao 2 DFA 14
III.3. GIAO DIỆN CHƯƠNG TRÌNH: 15
III.3.1 .Cài đặt dựa theo trạng thái tương đương 15
III.3.2 .Dựa vào tính đóng của phép giao 2 DFA 16
III.4. Cài đặt 17
III.4.1 Cài đặt dựa theo trạng thái tương đương 18
III.4.2 Cài đặt dựa vào tính đóng của phép giao 2 DFA 20

GVHD:TS Hà Chí Trung
Trang 2
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
II. CƠ SỞ LÝ THUYẾT
II.1. Định nghĩa DFA
II.1.1. Mô tả không hình thức
Automat hữu hạn đơn định là một cái máy đoán nhận xâu. 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:
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).
GVHD:TS Hà Chí Trung
Trang 3
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
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 song 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 đó.

. DFA bây giờ ở trạng thái q
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 q
n
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.
GVHD:TS Hà Chí Trung
Trang 4
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
II.1.4. Các cách biểu diễn đơn giản hơn của DFA
Cho một automata thực chất là cho hàm chuyển trạng thái của nó, có thể
cho dưới dạng bảng chuyển trạng thái hoặc cho dưới dạng đồ thị chuyển.
a. Bằng đồ thị có hướng:
Đồ thị chuyển là một đa đồ thị có hướng (có thể có khuyên) G:
+ Tập đỉnh của G được gán nhãn bởi các phần tử thuộc Q,
+ Các cung được gán nhãn bởi các phần tử thuộc Σ, nếu a ∈ Σ, p,q ∈ Q và
δ(q, a) = p thì sẽ có một cung từ đỉnh q tới đỉnh p được gán nhãn a.
+ Đỉnh vào của đồ thị chuyển ứng với trạng thái ban đầu q

(p, w) và δ
*
(q, w) cho kết quả hoặc cùng là trạng thái kết thúc hoặc
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ỉ 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.
• Để 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:
Bước 1: 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.
Bước 2: 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.
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 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.
GVHD:TS Hà Chí Trung
Trang 6
Môn học Automat và NNHT Đề tài: Hai DFA tương đươ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.


*Định lý: Nếu L
1
và L
2
là các ngôn ngữ chính quy thì L
1
∩ L
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

.
- Bảng chữ của M sẽ là hợp của các bảng chữ của M
1
và M
2
.
GVHD:TS Hà Chí Trung
Trang 8
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
- Một dịch chuyển trong M được xây dựng tương ứng một dịch chuyển
đồng thời trên M
1
và M
2
khi đọc cùng một kí hiệu.
- M sẽ đoán nhận xâu vào khi đồng 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

nhận w khi δ
1

*
(q
01
, w) ∈ F
1
và δ
2

*
(q
02
, w) ∈ F
2
, 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

L
=
2
L
thì
1
L
∩
2
L
=
1
L
∩
2
L
= L(M) = ∅.
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ụDFA biểu diễn
1
L
DFA biểu diễn
2
L
GVHD:TS Hà Chí Trung
Trang 10
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
DFA biểu diễn
2

tương đương có 2 cách nên chia làm 2 phần khác nhau.
GVHD:TS Hà Chí Trung
Trang 12
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
- Cả 2 cách đều có khả năng lấy dữ liệu từ File text,có khả năng Thêm, Sửa,
Xóa dữ liệu, hoặc nhập trực tiếp dữ liệu từ màn hình, với bảng hiện thị dữ liệu là
DataGridView.
III.1.1. Cài đặt dựa theo trạng thái tương đương
 Hàm: NhapDuLieuVaoMang() Nhập dữ liệu từ file text vao
mảng để tính toán.
 Hàm: TaoMang(int [,] mt,int m) Lấy ra 1 dòng từ ma trận,
lưu vào mảng.
 Hàm : SS2Hang (int [,] d1,int [,] d2,int h1,int h2) So sánh 2
dòng.
 Hàm : TimTrangThaiCuoi (int [,] d,int g) Tìm trạng thái kết
thúc.
 Hàm: SS2TT_BatKy( int [,] d1,int [,] d2,int n1,int n2) So
sánh 2 trạng thái bất kỳ.
 Ngoài ra trong bài còn có các Hàm hiển thị ma trận ra
textbox, nhằm minh họa rõ ràng về dữ liệu nhập.
III.1.2. Dựa vào tính đóng của phép giao 2 DFA
 Hàm: : NhapDuLieuVaoMang() Nhập dữ liệu từ file text
vao mảng để tính toán.
 Hàm: DFA_PhanBu2(int [,] d2 ,int n2 ) Kiểm tra phần bù
của DFA2.
 Hàm: DFA_PhanBu1(int[,] d1, int n1) ) Kiểm tra phần bù
của DFA1.
 Hàm: Dem_0(int [,]d1,int n1,int m) Đếm các giá trị 0 của
các giá trị nhập vào.
 Hàm: KiemTra(int [,] d1,int [,]d2,int n1,int n2)

kq2 = KiemTra(d1, d2, n1, n2)
kq1 + kq2 = 2 ?
Hiển Thị Ma Trận
Hiển Thị Kết Quả
Kết Thúc
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
III.3.2 .Dựa vào tính đóng của phép giao 2 DFA
*Giao diện chính:
GVHD:TS Hà Chí Trung
Trang 16
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
III.4. Cài đặt
Chú ý:
Dùng ma trận để mã hóa 2DFA
GVHD:TS Hà Chí Trung
Trang 17
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
+ Ma trận có 3 cột, số hàng là số các trạng thái: cột 1 là trạng thái Q, cột 2
thể hiện hàm δ (Q, 0), cột 3 thể hiện hàm δ(Q, 1).
+ Các trạng thái không kết thúc được mã hóa là số 1, trạng thái kết thúc
được mã hóa là số 0.
Dùng cho các DFA không có trạng thái mồ côi, trạng thái kết thúc vẫn có
hàm δ.
III.4.1 Cài đặt dựa theo trạng thái tương đương
 Hàm: NhapDuLieuVaoMang () . Nhập dữ liệu từ file text vao mảng để
tính toán.
private void NhapDuLieuVaoMang()
{
n1 = Convert.ToInt32(this.txt_SoTragThai_DFA_1.Text);
n2 = Convert.ToInt32(this.txt_SoTrangThai_DFA_2.Text);

int[] Mang1Chieu1 = TaoMang(d1, h1);
int[] Mang1Chieu2 = TaoMang(d2, h2);
for (int l = 0; l < Mang1Chieu1.Length; l++)
{
if (Mang1Chieu1[l] != Mang1Chieu2[l])
{
kt = 0;
}
// return 0;
}
Return kt
}
 Hàm : TimTrangThaiCuoi ( int [,] d , int g ) Tìm trạng thái kết thúc.
private int TimTrangThaiCuoi (int [,] d,int g)
{
int ViTriTTCuoi = 0;
for(int s=0;s<g;s++)
{
if(d[g,s]==0)
{
ViTriTTCuoi = s;
}
}
return ViTriTTCuoi;
}
 Hàm: SS2TT_BatKy ( int [,] d1 , int [,] d2 , int n1 , int n2 ). So sánh 2 trạng thái
bất kỳ.
private int SS2TT_BatKy( int [,] d1,int [,] d2,int n1,int n2)
{
int dem=0;int kt_Min =0;

for (int j = 0; j < 3; j++)
{
if (d2[i, j] == 1)
{
d2[i, j] = 0;
}
else
{
d2[i, j] = 1;
}
}

}
GVHD:TS Hà Chí Trung
Trang 20
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
 Hàm: DFA_PhanBu1 ( int [,] d1 , int n1 ) ) Kiểm tra phần bù của DFA1.
private void DFA_PhanBu1(int[,] d1, int n1)
{
for (int i = 0; i < n1; i++)
for (int j = 0; j < 3; j++)
{
if (d1[i, j] == 1)
{
d1[i, j] = 0;
}
else
{
d1[i, j] = 1;
}

Trang 22
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
KẾT LUẬN
Đối với mỗi người làm tin học, các ngôn ngữ là một phần không thể thiếu
trong công việc. Để có thể hiểu sâu sắc về các ngôn ngữ lập trình (giải thuật và
cú pháp) thì không thể không ngiên cứu về các ngôn ngữ hình thức, về các văn
phạm và các Outomat . Cũng chính vì vậy Automata và Ngôn Ngữ Hình Thức
được đưa vào làm môn học cho tất cả các sinh viên công nghệ thông tin .
Trong suốt quá trình làm ĐỒ ÁN MÔN HỌC, với sự cố gắng của từng thành
viên trong nhóm. Chúng em đã hoàn thành được ĐỒ ÁN MÔN HỌC này, đồng
thời qua Đồ án môn học kỹ năng lập trình đã có nhiều tiến bộ, cũng như khả
năng làm việc theo nhóm được nâng cao. Tuy nhiên chương trình không thể
tránh khỏi những sai sót. Chúng em vọng sẽ nhận được nhiểu hơn những sự
đóng góp từ phía thầy để chương trình này được hoàn thiện hơn!
Qua đây chúng em cũng muốn gửi lời cám ơn đến thầy Hà Chí Trung đã tận
tình hướng dẫn và giúp đỡ chúng em hoàn thành bài tập lớn này .
Chúng em xin chân thành cảm ơn!
GVHD:TS Hà Chí Trung
Trang 23
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
GVHD:TS Hà Chí Trung
Trang 24
Môn học Automat và NNHT Đề tài: Hai DFA tương đương
TÀI LIỆU THAM KHẢO
1. Giáo trình Lý thuyết ngôn ngữ hình thức và Automat – Nguyễn Thanh
Bình- Khoa CNTT- trường ĐHBK- ĐH Đà Nẵng.
2. Bài giảng của GVHD TS Hà Chí Trung.
GVHD:TS Hà Chí Trung
Trang 25