Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
TRƯỜNG ĐẠI HỌC KỸ THUẬT TP.HỒ CHÍ MINH
KHOA CÔNG NGHỆ THÔNG TIN
LUẬN VĂN TỐT NGHIỆP
Đề tài
Chương trình trợ giúp học một số
giải thuật trong môn học
Thầy hướng dẫn :
HỒ VĂN QUÂN
QUẢN THÀNH THƠ
Sinh viên thực hiện :
NGUYỄN CÔNG MINH
LƯU THỊ TỐT
Lớp KS2 – K6
7/99
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 89
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
MỤC LỤC
1 .Phần một
Lý thuyết ngôn ngữ hình thức và Ôtômát phần ngôn ngữ chính qui
1.1 Chương 1: Một số kiến thức lý thuyết cơ bản của môn học 2
1.1.1 Từ (word) 2
1.1.2 Ngôn ngữ 3
1.1.3 Automata (máy tự động ) 3
1.1.4 Biểu thức chính qui và ngôn ngữ chính qui 4
1.1.5 Văn phạm chính qui 5
1.2 Chương 2 : Một số giải thuật liên quan 7
1.2.1 Chuyển Nfa sang DFA 7

1.2.2 Xây dựng NFA từ Biểu thức chính qui 12
1.2.3 Xây dựng NFA từ Văn phạm chính qui 18
1.2.4 Giải thuật rút gọn số trạng thái của DFA 19
1.3 Chương 3 :Borland Delphi 3.0 21
1.3.1 Giới thiệu 21
1.3.2 Phần chủ yếu sử dụng trong chương trình 22
2. Phần hai
Phân tích và thiết kế tổng quát
2.1 Chương 1: Lý thuyết về phần mềm giảng dạy 26
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 90
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
2.1.1 Phần mềm giảng dạy 26
2.1.1.1 Phần mềm dạy học 26
2.1.1.2 Các loại phần mềm giảng dạy hiện tại 27
2.1.1.3 Ứng dụng lý thuyết CDT trong thiết kế phần mềm giảng dạy 28
2.1.2 Chương trình trợ giúp giảng dạy môn ngôn ngữ lý thuyết và Automat
hình thức 28
2.1.2.1 Phân tích các điều kiện giảng dạy 28
2.1.2.2 Phương pháp giảng dạy. Chiến lược phát triển các mô hình cho
môn học 29
2.2 Chương 2 : Chương trình trợ giúp giảng dạy Lý thuyết ngôn ngữ hình thức
và Automat. Phân tích và thiết kế tổng quát 35
2.2.1 Chương trình này làm gì 35
2.2.2 Nhận dạng và xây dựng các đối tượng của phần mềm 36
3.Phần ba
Lập trình cụ thể xây dựng các đối tượng
3.1 Chương 1: Phân tích và thiết kế xây dựng các đối tượng 43
3.1.1Các đối tượng cần xây dựng 44

3.1.1.1 Các đối tượng đồ họa 44
3.1.1.2 Các đối tượng lý thuyết 44
3.1.1.3 Các đối tượng liên kết 44
3.1.2 Sơ đồ tổng quát_ Hướng đi của chương trình 47
3.1.3 Chiến lược xây dựng các Module độc lập 48
3.1.4 Chỉ dẫn bảng thiết kế 49
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 91
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
3.2 Chương 2 : Cấu trúc dữ liệu của các dối tượng 50
3.2.1.Đối tựợng Nfa Bằng hình vẽ 50
3.2.1.1Tổ chức dữ liệu và cây phân cấp các đối tượng hình 51
3.2.2.2 Dữ liệu và thuật giải 58
3.2.2 Đối tượng DFA bằng hình vẽ 63
3.2.3 Đối tượng NFA lý thuyết bộ 5 63
3.2.4 Đối tượng DFA lý thuyết bộ 5 66
3.2.5 Đối tượng Biểu thức chính qui 67
3.2.6 Đối tượng Văn phạm chính qui 68
3.3 Chương 3 : Các giải thuật 70
3.3.1 Trình biên dòch cho biểu thức chính qui 71
3.3.2 Kiểm tra lỗi cho Văn phạm chính qui 74
3.3.3 Giải thuật xây dựng DFA từ NFA 75
3.3.4 Giải thuật rút gọn số trạng thái của DFA 76
3.3.4 Giải thuật sinh ra NFA từ Biểu thức chính qui 77
3.3.5 Giải thuật sinh ra NFA từ Văn phạm chính qui 78
3.4 Chương 4 :Giao diện chương trình 84
3.4 Chương 5 :Tìm hiểu Winhelp .Xây dựng Help- cho ứng dụng 84
3.5.1 Tìm hiểu Winhelp 84
3.5.2 Xây dựng Help cho ứng dụng 85

4 Phần bốn
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 92
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Chương trình nguồn 89
Hết 198
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 93
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Lời nói đầu
Lý thuyết ngôn ngữ hình thức và automat là môn lý thuyết bắt nguồn từ
những nhu cầu mô phỏng ngôn ngữ tự nhiên sử dụng trong máy tính. Ta khó có
thể nói hết những ứng dụng của môn học lý thuyết ngôn ngữ hình thức và
automata trên các lónh vực khác nhau của khoa học máy tính như trình biên
dòch, trong kỹ thuật nhận dạng và chuyển đổi giữa các ngôn ngữ khác nhau.
Chính vì việc nghiên cứu và ứng dụng Lý thuyết ngôn ngữ hình thức và
automata có một vai trò quan trọng như thế, nên việc xây dựng một chương
trình trợ giúp học cho môn học này sẽ có một vai trò tích cực nhất đònh, nhất là
đối với các sinh viên thuộc khoa Công nghệ thông tin. Ngay cả khi chương trình
được xây dựng với nhiều hạn chế, thì nó cũng sẽ để lại những kinh nghiệm để
có thể cải thiện và xây dựng lại một chương trình tốt hơn. Vì như đã nói, với
tầm quan trọng của Lý thuyết ngôn ngữ hình thức và automata, với sự phát
triển như vũ bão của lónh vực công nghệ thông tin ngày nay, một chương trình
hướng dẫn trợ giúp học môn Lý thuyết ngôn ngữ hình thức và automata nhất
đònh phải được ra đời và sẽ liên tục được phát triển, nâng cấp cũng như được sử
dụng rộng rãi.
Đấy cũng là mục đích của luận văn này. Có thể chương trình được xây
dựng trong luận văn chưa phải là một mô hình trợ giúp cho việc học tối ưu nhất.

Nhưng với nó chúng tôi hy vọng rằng các bạn sẽ đỡ vất vã nhiều trong quá
trình tìm hiểu và học hỏi một số giải thuật cơ bản của môn Lý thuyết ngôn ngữ
hình thức và automata. Chương trình được hình thành từ những ý tưởng hỗ trợ
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 94
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
việc học giúp các bạn học viên thông qua nó để tìm hiểu những vấn đề về lý
thuyết (cụ thể là sử dụng Help của chương trình) ; cũng như tham khảo quá
trình chạy giải thuật của máy tính theo kiểu từng bước để nhằm nắm được sâu
hơn nội dung mà sách hay giáo trình của môn học đưa ra. Chúng tôi hy vọng
chương trình trở thành một công cụ kiểm tra bài tập và tự học các giải thuật
trong môn học này một cách sinh động nhầm nâng cao hiệu quả tiếp thu kiến
thức.
Ngõ hầu đạt được kết quả mong muốn chúng tôi đã cố gắng phân tích và
đề ra các phương pháp thực hiện phần mềm sử dụng sao cho gần gũi và thân
thiện với người học. Với sự cố vấn tận tình của Thầy Hồ Văn Quân và Thầy
Quản Thành Thơ, chúng tôi cố gắng tạïo đầy đủ các công cụ hổ trợ cho người sử
dụng trong khả năng cho phép của mình. Tuy vậy, chắc chắn chương trình sẽ có
phần hạn chế do những yếu tố chủ quan của các tác giả, nhưng chương trình có
thể phát triển thành một chương trình giảng dạy hoàn chỉnh cũng như có thể
được nghiên cứu để phát triển việc xây dựng các chương trình trợ giúp giảng
dạy cho các môn học khác.
Thành phố Hồ Chí Minh, 7/99.
Học viên KS2-K6

Nguyễn Công Minh
Lưu Thò Tốt
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 95

Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Chương 1
Một số kiến thức lý thuyết cơ bản của môn học.
1.1.1.Từ ø(word):
♦ Cho ∑ là bảng chữ cái (alphabet) , một từ w trên ∑ là 1 chuỗi hữu hạn
các chữ cái. Ví dụ u = aabba , v = ababaa là các từ trên bảng chữ cái
∑ = {a,b}.
♦ Chuỗi rỗng cũng là 1 từ trên bảng chữ cái ∑ , ký hiệu λ
♦ Toán tử kết nối (concatenation) : cho 2 từ u ,v trên bảng chữ cái ∑ , kết
nối của u và v , ký hiệu uv là 1 từ trên bảng chữ cái ∑ bao gồm các ký tự
thuộc u theo sau là các ký tự thuộc v .
♦ Một từ u được gọi là từ con (subword) của từ w nếu w = v
1
uv
2
.Nếu
v
1
= λ thì u được gọi là đoạn bắt đầu (initial segment) hay tiền tố (prefix)
của w.
♦ λ là từ con của w và w là từ con của chính nó.
♦ Chiều dài của 1 từ u ký hiệu
u
hay l(u) : là số phần tử trong chuỗi các
ký tự của nó.
♦ Với mọi từ u,v trên ∑ :

uv u v= +
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân

Trang 96
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát

uv vu=
♦ Cho F là tập các từ trên bảng chữ cái ∑ , thì F là semigroup với toán tử
kết nối và identity element là λ. F còn được gọi là free semigroup trên
∑.
1.1.2. Ngôn ngữ (language) :
♦ Bất kỳ 1 tập L các từ trên bảng chữ cái ∑ , hay tập con L của ∑
*
được gọi
là 1 ngôn ngữ.
♦ Cho K và L là 2 ngôn ngữ trên bảng chữ cái ∑ :
 KL là 1 ngôn ngữ trên ∑ chứa các từ có được bằng cách nối các từ
trong K với các từ trong L.
KL = {w : w = uv , u∈ K và v∈L}
 L
0
={λ} , L
1
= L và L
n
= L
n-1
L với n>0
 L
*
chứa tất cả các từ mà các ký tự là thuộc các từ trong L :
L

*
L
k
k 0
=
=
∞

1.1.3.Automata (máy tự động)
Một Automata là một mô hình trừu tượng của một máy tính số.Automata
có một đơn vò điều khiển (control unit) dò tìm kiểm tra chuỗi nhập .
1.1.3.1. Automata hữu hạn đơn đònh (dfa or deterministic finite accepter)
1.1.3.1.1. Đònh nghóa 1:
Một dfa được đònh nghóa bởi bộ năm:
M= (Q, ∑ ,δ, q
0
,F)
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 97
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
trong đó:
 Q: Tập hữu hạn các trạng thái trong.
 ∑: Tập hữu hạn các ký hiệu nhập.
 δ: Q×∑ > Q là hàm chuyển trạng thái.
 q
0
∈ Q: Trạng thái khởi đầu.
 F ⊆ Q: Tập các trạng thái kết thúc.
1.1.3.1.2. Hoạt động của dfa:

Đọc các ký tự của chuỗi từ trái sang phải đồng thời thay đổi trạng thái ở
ký tự cuối, nếu trạng thái trong ∈ F thì chấp nhận chuỗi, ngược lại thì
không.
1.1.3.1.3. Đònh nghóa 2:
Ngôn ngữ chấp nhận bởi dfa M= (Q, ∑ ,δ, q
0
,F) là tập tất cả các chuỗi
trên ∑ được chấp nhận bởi M. Biểu diễn chính thức bằng kí hiệu:
L(M) = {w ∈ ∑
*
: δ
*
(q
0
,w) ∈ F }
1.1.3.1.4. Đònh nghóa 3:
Một ngôn ngữ L được gọi là chính qui nếu và chỉ nếu tồn tại một dfa M
nào đó sau cho L = L(M).
1.1.3.2. Automata hữu hạn không đơn đònh (nfa or nondeterministic finite
accepter)
1.1.3.2.1.Đònh nghóa:
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 98
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Một nfa được đònh nghóa bởi bộ năm:
M= (Q, ∑ ,δ, q
0
,F)
trong đó:

 Q: Tập hữu hạn các trạng thái trong.
 ∑: Tập hữu hạn các ký hiệu nhập.
 δ: Q×(∑ ∪{λ}) > 2
Q
là hàm chuyển trạng thái.
 q0∈ Q: Trạng thái khởi đầu.
 F ⊆ Q: Tập các trạng thái kết thúc.
1.1.4. Biểu thức chính qui và ngôn ngữ chính qui :
♦ Cho bảng chữ cái ∑ và 5 ký tự đặc biệt : “(” ,” )” , “+” ,”*” , “λ” . Biểu
thức chính qui r và ngôn ngữ L(r) trên tập ∑ được đònh nghóa như sau :
1. Không có biểu thức chính qui có chiều dài là 0
2. Biểu thức chính qui có chiều dài là1làλ và mọi a∈∑,L(λ) ={λ}
và L(a)={a}.
3. Chỉ có 1 biểu thức chính qui có chiều dài là 2 là ( ) , và ngôn
ngữ mà nó đònh nghóa là tập rỗng.
4. Giả sử r là 1 biểu thức chính qui đònh nghóa ngôn ngữ L(r) , thì
(r) là biểu thức chính qui và L((r)) = L(r) , và (r*) là biểu thức
chính qui đònh nghóa ngôn ngữ L*
5. Giả sử r
1
và r
2
là 2 biểu thức chính qui đònh nghóa ngôn ngữ L
1
và L
2
, thì (r
1
+r
2

) là biểu thức chính qui đònh nghóa ngôn ngữ
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 99
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
L
1
∪L
2
, và (r
1
r
2
) là biểu thức chính qui đònh nghóa ngôn ngữ
L
1
L
2
♦ Tập chính qui hay ngôn ngữ chính qui L:L được gọi là chính qui nếu L
là ngôn ngữ được đònh nghóa bởi biểu thức chính qui r. Nghóa là tồn tại
một biểu thức chính qui r sao cho L =L(r) .
1.1.5.Văn phạm chính qui và ngôn ngữ chính qui:
Để nghiên cứu ngôn ngữ ,chúng ta cần một cơ chế mô tả nó. Ngôn ngữ
hằng ngày thường là không chính xác (vì có thể hiểu theo nhiều nghóa
tùy hoàn cảnh và tùy mỗi người) và nhập nhằng không rõ ràng (câu có
thể không xác đònh được ý nghóa chính xác), vì vậy chúng ta sẽ học về
một vài cơ chế đònh nghóa ngôn ngữ mà rất hữu hiệu trong các trường
hợp khác nhau đó là văn phạm.
1.1.5.1.Văn phạm:
1.1.5.1.1.Đònh nghóa 1:

Một văn phạm G được đònh nghóa như là một bộ bốn:
G = (V,T,S,P)
trong đó:
 V là một tập hữu hạn các đối tượng được gọi là các biến
(variable)
 T là tập hữu hạn các đối tượng được gọi là các kí hiệu kết thúc
(terminal symbol)
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 100
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
 S ∈ V là một kí hiệu đặc biệt được gọi là biến khởi đầu (start
variable)
 P là tập hữu hạn các luật sinh (production)
Các luật sinh là trái tim của văn phạm, chúng chỉ ra làm thế nào văn
phạm biến đổi một chuỗi thành một chuỗi khác , và thông qua cách này
chúng (các luật sinh ) đònh nghóa một ngôn ngữ liên kết với văn phạm.
1.1.5.1.2.Văn phạm tuyến tính – Phải và – Trái :
1.1.5.1.2.1.Đònh nghóa 2:
Một văn phạm G = (V,T,S,P) được gọi là tuyến tính – phải nếu tất cả
luật sinh có dạng
A → xB,
A → x.
Trong đó A,B ∈ V , x ∈ T
*
. Một văn phạm là tuyến tính – trái nếu tất cả
các luật sinh là có dạng
A → Bx,
A → x.
Một văn phạm chính qui là văn phạm mà hoặc là tuyến tính – phải hoặc

là tuyến tính – trái.
1.1.5.1.2.2.Đònh lý:
Một ngôn ngữ L là chính qui nếu và chỉ nếu tồn tại một văn phạm chính
qui G sao cho L = L(G).
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 101
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Chương 2
Một số giải thuật liên quan.
1.2.1.Chuyển NFA sang DFA tương đương:
1.2.1.1.Giải thuật tập con (tạo DFA và NFA)
 Nhập:
Một automaton hữu hạn không đơn đònh nfa gọi tắt là N
 Xuất:
Một automaton hữu hạn đơn đònh dfa gọi tắt là D nhận dạng cùng
một ngôn ngữ như nfa.
 Phương pháp:
Giải thuật này là xây dựng bảng truyền cho dfa. Mỗi trạng thái
của dfa là tập trạng thái của nfa và ta xây dựng bảng truyền sao
cho dfa mô phỏng đồng thời tất cả các chuyển động của nfa trên
chuỗi nhập cho trước.
Chúng ta dùng các tác vụ sau để lưu giữ các tập trang thái của nfa:
Tác vụ Giải thích
-closure(qo) Là tập trạng thái của nfa, nfa đạt được chúng từ
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 102
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
trạng thái qo trên sự truyền rỗng.

-closure(T) Là tập trạng thái của nfa , nfa đạt tới chúng từ
một trạng thái q nào đó của nfa thuộc T trên sự
truyền rỗng .
Move(T,a) Tập các trạng thái nfa, nfa đạt được chúng khi
có sự truyền trên kí hiệu nhập.
 Phân tích:
Trước khi đọc một kí tự nhập, nfa có thể ở một trạng thái bất kỳ
trong các trạng thái thuộc -closure(q
0
). q
0
là trạng thái bắt đầu
của nfa. Giả sử các trạng thái của T là các trạng thái đạt được từ
q
0
trên các kí tự nhập và giả sử a là kí tự nhập kế tiếp. Khi đọc a,
nfa có thể chuyển đến một trạng thái bất kỳ trong tập trạng thái
move(T,a). Khi chúng ta cho phép sự truyền rỗng, nfa có thể ở bất
kỳ trạng thái nào trong tập -closure (move(T,a)) sau khi đã đọc a.
 Giải thuật: Xây dựng tập con
Bắt đầu -closure(q
0
) chỉ là một trạng thái trong các trạng thái
của dfa, chưa được đánh dấu.
while có một trạng thái T. chưa được đánh dấu trong dfa do
Begin
Đánh dấu T; {đánh dấu có nghóa là đem T ra xét}.
For với mỗi kí tự nhập a do
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 103

Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
begin
U:= -closure (move(T,a));
If U không có trong tập trạng thái của
dfa then
begin
Thêm U vào các trạng
thái của dfa, và là trạng
thái chưa được đánh dấu;
U(T,a):= U{D[T,a] là
phần tử của bảng truyền
của dfa} ;
end;
end;
end;
Chúng ta xây dựng các trạng thái của dfa và xây dựng bảng truyền cho
dfa theo mẫu sau:
Mỗi trạng thái của dfa tượng trưng cho tập trạng thái của nfa, mà
nfa có thể ở trong đó sau khi đọc chuỗi các kí hiệu nhập bao gồm:
tất cả sự truyền rỗng có thể xãy ra trước hoặc sau các kí hiệu được
đọc. Trạng thái bắt đầu của dfa là -closure(q
0
). Các trạng thái và
sự truyền sẽ được thêm vào dfa bằng giải thuật xây dựng tập con
trên . Một trạng thái của dfa là trạng thái kết thúc nếu nó là tập
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 104
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát

các trạng thái của nfa chứa đựng ít nhất một trạng thái kết thúc
của nfa.
 Giải thuật: Tính -closure.
Đẩy tất cả các trạng thái trong T vào stack;
Khởi tạo -closure(T) cho T;
while stack không rỗng do
begin
Lấy t. là phần tử trên đỉnh stack;
for mỗi trạng thái u với cạnh đi từ t đến u có tên do
if u không phải thuộc -closure(T) then
begin
Thêm u vào -closure(T);
Đẩy u vào stack
end;
end;
Việc tính toán -closure(T) là quá trình tìm kiếm một đồ thò của các nút
từ các nút cho trước và đồ thò bao gồm toàn là các cạnh có tên của nfa.
Giải thuật đơn giản để tìm -closure(T) là dùng stack để giữ các trạng
thái mà cạnh của chúng chưa được kiểm tra cho sự truyền rỗng như giải
thuật tính -closure trên.
1.2.1.2.Ví dụ :
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 105
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Một nfa như hình (dưới) nhận dạng ngôn ngữ (a|b)*abb. Chúng ta áp
dụng giải thuật xây dựng tập con để xây dựng dfa tương đương. Trạng
thái bắt đầu của dfa là -closure(q
0
) là A= {q

0
,q
1
, q
2
, q
4
, q
7
}. Tập chữ
cái nhập là {a,b}.
♦ Bây giờ tính -closure (move(A,a))
♦ Trước tiên chúng ta tính move(A,a), nó sẽ là tập trạng thái của nfa có
sự truyền trên kí tự nhập a.
Trong các trạng thái của A: q
0
,q
1
, q
2
, q
4
, q
7
chỉ có q
2
, q
7
là có sự truyền
trên a q

3
, q
8
là hai trạng thái đạt từ q
2
va øq
7
trên a. Vậy:
-closure (move ({q
0
,q
1
, q
2
, q
4
, q
7
},a)) = -closure({q
3
, q
8
})
= { q
1
, q
2
, q
3
, q

4
, q
6
, q
7
, q
8
}
Ta gọi tập đó là B. Vậy D[A,a] = B
 Trong các trạng thái của A chỉ có trạng thái q
4
có sự truyền
trên kí tự nhập b, đến trạng thái q
5
. Như vậy
-closure (move(A,b)) = -closure ({q
5
})
= { q
1
, q
2
, q
4
, q
5
, q
6
, q
7

} = C
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 106
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Vậy : D[A,b] = C = { q
1
, q
2
, q
4
, q
5
, q
6
, q
7
}
Ta có thể tiếp tục quá trình này, và như vậy có thể lên đến 2
11
tập
con khác nhau của tập 7 trạng thái . Thực tế ở đây ta có 5 tập con ,
mà chúng ta đã tạo ra :
A = {q
0
,q
1
, q
2
, q

4
, q
7
}
B = { q
1
, q
2
, q
3
, q
4
, q
6
, q
7
, q
8
}
C = { q
1
, q
2
, q
4
, q
5
, q
6
, q

7
}
D = { q
1
, q
2
, q
4
, q
5
, q
6
, q
7
, q
9
}
E = { q
1
, q
2
, q
4
, q
5
, q
6
, q
7
, q

10
}
Từ tập trạng thái này ta thấy A là trạng thái bắt đầu (đặt A:= q
0
của dfa), E := q
4
trạng thái kết thúc của dfa và bảng truyền như
sau:
Với:
A:= q
0
, B:= q
1
, C:= q
2
, D:= q
3
, E:= q
4
,
Bảng truyền cho dfa
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 107
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
Từ bảng truyền trên ta xây dựng mộât dfa ,nhận dạng ngôn ngữ (a|b)*abb:
DFA nhận dạng ngôn ngữ (a|b)*abb
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 108
Luận văn tốt nghiệp KS2 – K6 :

Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
1.2 .2 .Xây dựng nfa từ biểu thức chính qui:
Giải thuật mà chúng ta trình bày để xây dựng nfa từ biểu thức chính qui
gọi là trực tiếp cú pháp (syntax-directed) bởi gì nó dùng cấu trúc cú pháp
của các biểu thức chính qui để trợ giúp cho việc xây dựng nfa
♦ Giải thuật cho phép các đònh nghóa của biểu thức chính qui.
♦ Trước tiên ta xây dựng automaton để nhận dạng kí tự rỗng và kí tự
của bộ kí tự cơ bản.
♦ Sau đó ta sẽ xây dựng automaton cho các biểu thức chứa các phép
chọn ‘|’ nối kết ‘.’ và bao đóng ‘*’ .
Ở mỗi bước xây dựng sẽ xuất hiện thêm nhiều nhất là 2 trạng thái mới.
Như vậy automaton kết qua sẽ có nhiều nhất số trạng thái bằng hai lần
số kí hiệu cơ bản và các phép toán trên biểu thức chính qui.
1.2.2.1 . Giải thuật (cấu trúc ‘Thompson’).
Xây dựng nfa từ biểu thức chính qui.
♦ Phương pháp :
Trước tiên ta phân tích r thành các biểu thức nhỏ hơn ,sau đó ta dùng
qui tắc 1 và 2 dưới đây để xây dựng nfa cho mỗi một kí hiệu cơ bản
trong r. Nếu một kí hiệu a xuất hiện nhiều lần trong r thì nfa được xây
dựng cho mỗi lần xuất hiện a . Sau đó dựa vào cấu trúc cú pháp của
biểu thức chính qui r, ta kết hợp các nfa một cách qui nạp bằng qui
tắc 3 dưới đây cho tới khi ta có nfa của biểu thức chính qui r. Mỗi nfa
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 109
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
trung gian được sinh ra trong quá trình xây dựng sẽ đại diện cho biểu
thức con của r và có một số tính chất quan trọng : có một trạng thái
kết thúc , không có cạnh đi vào trạng thái bắt đầu, không có cạnh đi
ra từ trạng thái kết thúc .

♦ Qui tắc :
1. Với , xây dựng nfa :
i là trạng thái bắt đầu ; f là trạng thái kết thúc
nfa nhận dạng tập rỗng { }
2. Với a thuộc , xây dựng nfa:
i là trạng thái bắt đầu ; f là trạng thái kết thúc
nfa này nhận dạng {a}
3. Giả sử N(s) và N(t) là nfa cho biểu thức chính qui s và t.
a) Với biểu thức s | t xây dựng nfa hỗn hợp N(s | t)
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 110
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
i là trạng thái bắt đầu mới ; f là trạng thái kết thúc mới. Có sự
truyền từ i trên kí hiệu đến trạng thái bắt đầu của N(s) và
N(t) đồng thời có sự từ trạng thái kết thúc của N(t) và N(s)
đến trạng thái kết thúc mới f trên kí hiệu nhập . Trạng thái
bắt đầu và kết thúc của N(t) và N(s) không phải là trạng thái
bắt đầu và kết thúc của N(s | t) .
Chúng ta lưu ý là bất cứ một đường nào đi từ i đến f đều phải
đi qua hoặc N(s) hoặc N(t) như vậy rõ ràng nfa nhận dạng L(s)
U L(t).
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 111
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
b) Cho biểu thức chính qui s.t xây dựng nfa hỗn hợp.

Trạng thái kết thúc của N(t) là trạng thái kết thúc của nfa hỗn
hợp. Trạng thái kết thúc của N(s) sẽ lại chính là trạng thái bắt

đầu của N(t). Con đường đi từ i đến f bắt buộc trước tiên đi
qua N(s) và sau đó qua N(t). Như vậy tên của con đường là
một chuỗi thuộc L(s)L(t) không có một cạnh nào đi từ trạng
thái kết thúc N(s) và cũng không có cạnh nào đi vào trạng thái
bắt đầu của N(t). Không có con đường nào từ i đến f lại đi
vòng từ N(t) trở lại N(s), rõ ràng nfa hỗn hợp nhận dạng
L(s)L(t).
c) Để xây dựng nfa cho biểu thức chính qui s* ta có sơ đồ:
Ở đây trạng thái bắt đầu mới là i và trạng thái kết thúc mới là
f. Trong nfa chúng ta có thể đi từ i đến f trực tiếp theo cạnh có
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 112
Luận văn tốt nghiệp KS2 – K6 :
Chương trình trợ giúp học một số giải thuật trong môn học Lý thuyết ngôn ngữ hình thức & Ôtômát
nhãn ,điều đó nói lên thuộc (L(s))*, hoặc đi từ i đến f
thông qua N(s) một hoặc nhiều lần, rõ ràng nfa hỗn hợp nhận
dạng (L(s))*.
d) Với biểu thức chính qui (s) thì N(s) tự nó là nfa nhận dạng
L(s).
Với cách xây dựng này tại mỗi thời điểm chúng ta tạo trạng
thái mới có tên khác nhau . Như vậy không có hai trạng thái
nào có cùng tên mặc dầu chỉ có một kí hiệu, xuất hiện ở những
thời điểm khác nhau. Ta sẽ tạo cho mỗi trường hợp xuất hiện
của kí hiệu đó một nfa riêng biệt với những trạng thái của nó.
Chúng ta có thể khẳng đònh rằng mỗi bước của sự xây dựng theo giải
thuật Thompson sẽ sinh ra nfa nhận dạng ngôn ngữ đúng .
Thêm vào đó nfa , N(r) có các tính chất sau:
1. N(r) có nhiều nhất số trạng thái bằng 2 lần số các kí hiệu và các
phép toán trên r.
2. N(r) chỉ có một trạng thái bắt đầu và một trạng thái kết thúc. Từ

trạng thái kết thúc không có sự truyền . Tính chất này thỏa mãn
cho từng automaton .
3. Mỗi trạng thái của N(r) sẽ có một sự truyền từ trạng thái đó trên
kí hiệu thuộc hoặc nhiều nhất 2 sự truyền từ trạng thái đó trên
kí hiệu .
1.2.2.2.Ví du ï:
SVTH : Nguyễn Công Minh -– Lưu Thò Tốt GVHD : Quản Thành Thơ - Hồ Văn Quân
Trang 113