1
Chương 3:
VĂN PHẠM CHÍNH QUY
VÀ
ÔTÔMÁT HỮU HẠN
2
Nội dung
1. Ôtômát hữu hạn đơn định - DFA.
2. Ôtômát hữu hạn không đơn định - NFA.
3. Sự tương đương của NFA và DFA
4. Mối liên quan giữa VPCQ và OH
5. OHD không xuất phát lại
6. Các tính chất đóng của ngôn ngữ chính quy.
7. Định lý KLEENE.
8. Biểu thức chính quy.
9. Thuật toán Thampson
Ôtômát hữu hạn đơn định – DFA
(Deterministic Finite Automata)
Mô tả phi hình thức:
Ôtômát hữu hạn như một “máy” đoán nhận chuỗi, nó
làm việc như sau:
Băng từ chia thành nhiều ô. Mỗi ô có khả năng lưu
trữ một ký hiệu của chuỗi nhập (chuỗi cần được
đoán nhận w є *).
Có một đầu đọc, ở mỗi thời điểm quan sát một ô trên
băng từ.
Có một bộ điều khiển Q gồm tập hợp hữu hạn trạng
thái; ở mỗi thời điểm có một trạng thái hiện hành gọi
là trạng thái nội.
3
4
Tùy theo cấu hình hiện tại gồm (trạng thái hiện thời của bộ điều
khiển và ký hiệu trên ô mà đầu đọc quan sát được), mà Ôtômát
chuyển sang 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 sang trạng thái mới, được cho bởi một hàm,
gọi là hàm chuyển trạng thái : Q x Q.
0 1 1 0 0 1 1 1 1
q Bộ điều khiển
Băng từ sức chứa vô hạn
Input : w *
Output : Yes, w L
No, w L
2
5
Trong Q có phân biệt q0 Q, gọi là trạng thái đầu và một tập
hợp F chứa các trạng thái kết thúc.
Ta nói ôtômát đoán nhận (hay thừa nhận) một chuỗi vào w
*, nếu xuất phát từ q0, đầu đọc nhìn vào ký hiệu bên trái
nhất của w, sau một số bước hữu hạn làm việc, nó đọc xong
chuỗi w và rơi vào một trong các trạng thái kết thúc.
Tập hợp mọi chuỗi (được đoán nhận bởi Ôtômát) hợp thành
ngôn ngữ được đoán nhận bởi ôtômát đó.
Do Q là hữu hạn và hàm chuyển là hàm toàn phần và đơn
trị, cho nên bước chuyển của Ôtômát được xác định một
cách duy nhất. Chính vì vậy mà Ôtômát mô tả như trên được
gọi là ôtômát hữu hạn đơn định.
6
Định nghĩa hình thức: Một ôtômát hữu hạn đơn định (viết tắt là
ÔHĐ) là một hệ thống M = (, Q, , q0, F) trong đó:
là một bộ chữ cái hữu hạn, gọi là bộ chữ vào.
Q là một tập hữu hạn các trạng thái, Q = .
: Q x Q, được gọi là hàm chuyển.
q0 Q là trạng thái đầu.
F Q là tập các trạng thái cuối.
7
Ví dụ 3.1: Xét Ôtômát hữu hạn đơn định M(,Q, ,q0,F). trong đó:
= {0, 1}
Q = {q0, q1, q2, q3}
F = {q0}
Hàm cho bởi ma trận sau:
0 1
q0 q2 q1
q1 q3 q0
q2 q0 q3
q3 q1 q2
Ký hiệu vào
Trạng thái
Biểu diễn hàm chuyển trạng
Có 3 cách biểu diễn hàm chuyển (hàm chuyển trạng thái):
Theo định nghĩa (qi,a)=qj
Theo bảng truyền
Theo đồ thị
8
3
9
Để cho dễ hình dung hơn, ta thường biểu diễn hàm chuyển dưới
dạng một đồ thị định hướng, gọi là biểu đồ chuyển như sau:
Mỗi nút tương ứng với một trạng thái.
Nút đầu trỏ bởi mũi tên có chữ “Bắt đầu”.
Nút cuối được khoanh bởi hai vòng tròn.
Nếu (q, a) = p thì có một cung đi từ nút q tới nút p, và cung
đó mang nhãn a.
q0
q1
q1
Bắt đầu
a
q p
Biểu đồ chuyển cho Ôtômát hữu hạn nói ở trên (Ví dụ 3.1) sẽ
như sau:
q0
q2 q3
q1
Đầu
1
1
1
1
0 0 0 0
10
Tính chất của hàm chuyển trạng
1. (q,)=q
2. (q,wa)= ((q,w),a)
3. (q,aw)= ((q,a),w), w * và a
4. (q,xy)= ((q,x),y), x,y *
11
Định nghĩa tập đoán nhận bởi (M)
Ký hiệu T(M)
T(M) = { w | w * , (q0,w) = qf F }
Ví dụ:
w1 = 1010
w2 = 11001001
W3 = 110101
12
4
Ta gọi một hình trạng của ÔHĐ là một chuỗi có dạng qx
với q Q và x *.
VD: q0w3 = q0 110101 là một hình trạng của (M)
Quá trình đoán nhận một chuỗi của ÔHĐ là quá trình
biến đổi các hình trạng, thực chất là quá trình “viết lại”
chuỗi.
VD: Viết quá trình đoán nhận chuỗi x = 110101
13
14
Quá trình đoán nhận chuỗi vào
Cho chuỗi w= 110101. Quá trình đoán nhận chuỗi vào đó
diễn tả bằng các bước chuyển sau:
110101 110101 110101 110101 110101 110101
q0 q1 q0 q2 q3 q1 q0 F
Vì q0F, vậy chuỗi vào w=110101 được thừa nhận bởi Ôtômat.
Nhận xét rằng mỗi trạng thái của M ghi nhớ một tình trạng nhất
định của phần chuỗi vào đã đọc như sau:
q0: phần đã đọc chứa một số chẵn con số 0 và một số chẵn con số 1.
q1: phần đã đọc chứa một số chẵn con số 0 và một số lẻ con số 1.
15
Tập các chuỗi được ôtômát thừa nhận
q2: phần đã đọc chứa một số lẻ con số 0 và một
số chẵn con số 1.
q3: phần đã đọc chứa một số lẻ con số 0 và một
số lẻ con số 1.
Mỗi lần đọc thêm một ký hiệu 0 hay 1, hàm luôn
luôn chuyển trạng thái của ôtômát về đúng tình trạng
trên. Vì F = {q0}, cho nên các chuỗi được M thừa
nhận là các chuỗi có chứa một số chẵn con số 0
và một số chẵn con số 1.
16
Ngôn ngữ đoán nhận (thừa nhận) bởi M
Ngôn ngữ đoán nhận (hay thừa nhận) bởi M là:
L(M) = {w| w * và q0w * p với p F}
Trở lại ví dụ 3.1, hệ viết lại ngầm định của nó gồm các sản
xuất sau:
q00 q2 q10 q3 q20 q0 q30 q1
q01 q1 q11 q0 q21 q3 q31 q2
Quá trình đoán nhận chuỗi w = 110101 là:
q0110101 q110101 q00101 q2101 q301 q11 q0 F
Có một cách viết khác (thường thấy ở các sách khác):
(q0,110101)=(q1,10101)=(q0,0101)=(q2,101)=(q3,01)= (q1, 1)
= q0 F
5
17
Ôtômát hữu hạn không đơn định – NFA
(Nondeterministic Finite Automata)
Dễ dàng mở rộng mô hình ÔHĐ trên để cho hệ viết lại ngầm
định của Ôtômát là một hệ viết lại không đơn định, tức là có thể
chứa các sản xuất có cùng vế trái.
Định nghĩa: Ta gọi Ôtômát hữu hạn không đơn định (hay không
tiền định) viết tắt là ÔHK, là một hệ thống:
M = {, Q, , q0, F}
Trong đó: , Q, q0, F vẫn như tương tự OHĐ. Chỉ duy
nhất hàm là đổi lại: : Q x 2Q.
Hệ viết lại W = (V, P) ngầm định của M cũng có V = Q.
18
Ôtômát hữu hạn không đơn định (tt)
Tập đoán nhận bởi Ôtômat
T(M) = {w | w * và q0w * qf với qf F}.
Ngôn ngữ đoán nhận bởi M là:
L(M) = {w | w * và q0w * qf với qf F}.
Chuỗi vào w được (M) thừa nhận nếu tồn tại ít
nhất một quá trình dẫn xuất q0w * qf với qf
F.
Ví dụ 3.2: Xét ÔHK M = ({0,1}, {q0, q1, q2, q3,
q4}, , q0, {q2, q4}) với hàm chuyển cho như
sau:
19
Ôtômát hữu hạn không đơn định (tt)
Sau đây là quá trình đoán nhận chuỗi vào 01001, dẫn tới trạng
thái cuối q4:
q001001 q01001 q0001 q301 q41 q4 F
Đây chỉ là một quá trình đoán nhận trong nhiều quá trình.
0 1
q0 {q0, q3} {q0, q1}
q1 {q2}
q2 {q2} {q2}
q3 {q4}
q4 {q4} {q4}
Đầu
0, 1
q0
q1
q2
q3 q4
1
1
0 0
0, 1
0, 1
20
Ôtômát hữu hạn không đơn định (tt)
Nếu xét tất cả các quá trình, ta có một “cây” như sau:
q001001 q01001 q0001 q001 q01 q0
q31001 q1001 q301 q31 q1
q41 q4 F
Như vậy chuỗi 01001 đã thừa nhận bởi M.
Dễ thấy rằng ÔHK này thừa nhận các chuỗi trên {0, 1} có
chứa hai con 0 liên tiếp hoặc có chứa hai con 1 liên
tiếp.
L (M) = { w00w, w11w | w * ={0,1}*}