Giáo trình Automat và ngôn ngữ hình thức - Chương 3: Otomat hữu hạn và ngôn ngữ chính quy
Chương 3
OTOMAT HỮU HẠN VÀ NGÔN NGỮ CHÍNH QUY
Trong chương này, chúng ta sẽ nghiên cứu một mô hình “máy trừu tượng” để
đoán nhận ngôn ngữ, đó là các otomat hữu hạn. Chương này gồm các nội dung sau:
3.1. Otomat hữu hạn đơn định
. Ngôn ngữ được đoán nhận bởi otomat đơn định
3.2. Otomat hữu hạn không đơn định
. Ngôn ngữ đoán nhận bởi otomat không đơn định
. Đơn định hóa các otomat
. Sự tương đương giữa các otomat đơn định và không đơn định
3.3. Ngôn ngữ chính quy và biểu thức chính quy
. Sự liên hệ giữa otomat hữu hạn và ngôn ngữ chính quy
. Sự liên hệ giữa otomat hữu hạn và biểu thức chính quy
. Điều kiện cần của ngôn ngữ chính quy
73
3.1. OTOMAT HỮU HẠN ĐƠN ĐỊNH
Một otomat hữu hạn (Finite Automata-FA) là một mô hình tính toán thực
sự hữu hạn với sự mô tả quá trình tính toán bởi các input (đầu vào) và các output (đầu
ra). Tại mỗi thời điểm, hệ thống có thể được xác định bởi một trong số các cấu hình nội
tại, gọi là các trạng thái (state status). Mỗi trạng thái của hệ thống thể hiện tóm tắt các
thông tin liên quan đến những input đã chuyển qua hệ thống, và xác định các trạng thái
kế tiếp trên dãy input tiếp theo.
Mọi cái liên quan đến một otomat hữu hạn đều có kích thước hữu hạn, cố định, và
không thể mở rộng trong suốt quá trình tính toán. Các loại otomat khác được nghiên
cứu sau này có ít nhất một bộ nhớ vô hạn về tiềm năng. Sự phân biệt giữa các loại
otomat khác nhau chủ yếu dựa trên việc thông tin có thể được lưu trữ trong bộ nhớ như
thế nào.
Một otomat hữu hạn làm việc theo thời gian rời rạc, như vậy, ta có thể nói về thời
điểm “kế tiếp” khi đặc tả hoạt động của một otomat hữu hạn.
Tuy nhiên, nói chung, thông tin ra (output) sản sinh bởi một otomat hữu hạn phụ
thuộc vào cả thông tin vào hiện tại lẫn các thông tin vào trước đó. Như vậy otomat có
khả năng (với một phạm vi nào đó) ghi nhớ các thông tin vào trong quá khứ của nó. Một
cách chi tiết hơn, điều đó có nghĩa như sau: Mỗi otomat hữu hạn có một số hữu hạn
trạng thái được lưu ở bộ nhớ trong, tại mỗi thời điểm i, nó ở một trong các trạng thái đó,
chẳng hạn qi. Trạng thái qi+1 ở thời điểm sau được xác định bởi qi và thông tin vào ai
cho ở thời điểm i. Thông tin ra ở thời điểm i được xác định bởi trạng thái qi (hay bởi cả
ai và qi). Vì vậy, các otomat hữu hạn còn được gọi là các “máy trạng thái”.
Trong khoa học máy tính, ta có thể tìm thấy nhiều ví dụ về hệ thống trạng thái hữu
hạn, và lý thuyết về các otomat hữu hạn là một công cụ thiết kế hữu ích cho các hệ thống
này. Chẳng hạn, trường hợp đơn giản nhất là thiết bị không có bộ nhớ mà ở mỗi thời
điểm, thông tin ra chỉ phụ thuộc vào thông tin vào lúc đó. Các thiết bị như vậy là mô hình
của các mạch tổ hợp. Hay phức tạp hơn, mỗi trạng thái của một hệ thống chuyển mạch
với n cổng vào sẽ là một trong 2n phép gán của 0 và 1 với những giá trị của input, vì vậy,
mỗi bộ chuyển mạch có thể được xem là một hệ thống trạng thái hữu hạn.
Các máy tính hiện đại ngày nay cũng là các máy trạng thái hữu hạn, trạng thái
hiện tại của bộ xử lý trung tâm, bộ nhớ trong và các thiết bị lưu trữ liên quan ở mỗi thời
điểm bất kỳ là một số rất lớn nhưng hữu hạn của số các trạng thái. Và ngay cả bộ não
của con người cũng có thể được xem như một hệ thống trạng thái hữu hạn, vì số các nơ
ron thần kinh là số có giới hạn, số này không vượt quá 235
.
74
Các otomat hữu hạn được chia làm hai loại: otomat hũu hạn đơn định
(Deterministic Finite Automata-DFA) và otomat hữu hạn không đơn đinh
(Non deterministic Finite Automata-NFA), và đều có khả năng đoán
nhận các ngôn ngữ chính quy, là lớp ngôn ngữ có khả năng ứng dụng rất lớn trong việc
xây dựng các ngôn ngữ lập trình. Otomat đơn định có khả năng đoán nhận ngôn ngữ dễ
dàng hơn so với otomat không đơn định, nhưng otomat không đơn định lại có ưu điểm
là thuờng có cấu trúc đơn giản hơn. Điều quan trọng là lớp ngôn ngữ đoán nhận bởi hai
loại otomat này là tương đương.
Dưới đây chúng ta sẽ lần lượt nghiên cứu cả hai loại otomat này.
3.1.1. Định nghĩa otomat hữu hạn đơn định
Định nghĩa 3.1
Một otomat hữu hạn đơn định (Deterministic Finite Automata-DFA) là một bộ năm:
A = < Q, , , q0, F >
trong đó:
. Q là một tập hữu hạn khác rỗng, được gọi là tập các trạng thái (set of states);
. là một bảng chữ cái, được gọi là bảng chữ vào (input alphabet);
. : D Q, là một ánh xạ từ D Q × vào Q, được gọi là hàm chuyển trạng
thái (transition function);
. q0 Q, được gọi là trạng thái khởi đầu (starting state);
. F Q được gọi là tập trạng thái kết thúc (final states).
Nếu D = Q×, tức là hàm hai biến (q, a) xác định với mọi cặp giá trị (q, a), với
q Q, a thìta nói A là otomat đầy đủ, trái lại, nếu có những cặp giá trị (q, a) mà tại
đó hàm chuyển (q, a) không xác định, thì otomat A gọi là không đầy đủ. Sau này ta sẽ
thấy rằng mọi otomat hữu hạn đều đưa về được otomat hữu hạn đầy đủ tương đương.
Hoạt động của otomat hữu hạn đơn định A = <Q, , , q0, F> với một xâu vào
= a1a2… an có thể được mô tả như sau:
Khi bắt đầu làm việc, otomat ở trạng thái khởi đầu q0 và đầu đọc đang nhìn vào ô
có ký hiệu a1. Tiếp theo, dưới tác động của ký hiệu vào a1, otomat chuyển từ trạng thái
q0 về trạng thái mới q1 xác định bởi hàm chuyển, tức là (q0, a1) = q1 Q, và đầu đọc
chuyển sang phải một ô, tức là nhìn vào ô có ký hiệu a2. Sau đó otomat A có thể lại tiếp
75
tục chuyển từ trạng thái q1 nhờ hàm chuyển về trạng thái mới q2 = (q1, a2). Quá trình
đó sẽ tiếp tục cho tới khi gặp một trong các tình huống sau:
a). Otomat A đọc hết xâu vào và chuyển sang trạng thái qn, tức là A ở trạng thái
qn-1, đọc ký hiệu cuối cùng an và có (qn-1,an) = qn , khi đó nếu qn F, ta nói rằng A đoán
nhận xâu , trái lại nếu qn F thì ta nói otomat A không đoán nhận xâu .
b). Hoặc khi otomat A ở trạng thái qi nào đó, đọc đến ký hiệu aj của xâu vào, (j
n) và hàm chuyển (qi , aj) không xác định, khi đó otomat A dừng, ta cũng nói A không
đoán nhận xâu .
Chú ý rằng nếu A là otomat đầy đủ thì tình huống a). luôn xảy ra, tức là xâu
luôn được đọc hết, còn tình huống b). chỉ có thể xảy ra khi A là otomat không đầy đủ.
Hình 3.1 dưới đây mô tả quá trình đoán nhận xâu với tình huống otomat A đọc
hết xâu vào và chuyển vể trạng thái qn. Khi đó nếu qn F, ta nói rằng A đoán nhận
xâu , trái lại nếu qn F thì ta nói otomat A không đoán nhận xâu .
Xâu vào = a1
a2
a3
an-1
an
q0
q1
q2
…
qn-2
qn-1
qn
Hình 3.1. Mô tả quá trình đoán nhận xâu của otomat A
3.1.2. Biểu diễn otomat hữu hạn đơn định
Hàm chuyển trạng thái là một bộ phận quan trọng của một otomat hữu hạn đơn
định. Cho một otomat 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 hoặc cho dưới dạng đồ thị chuyển. Ứng với mỗi cách cho hàm
chuyển, ta có một cách biểu diễn otomat.
Biểu diễn otomat bằng bảng chuyển trạng thái
Cho ôtômát A = <Q, , , q0, F>, với Q = {q0, q1, q2,…, qm} là tập trạng thái, và
bảng chữ cái = {a1, a2,…, an}, khi đó hàm chuyển có thể cho bởi một bảng gồm m+1
hàng và n cột; trong đó ô (i, j) nằm trên dòng i cột j của bảng được ghi giá trị hàm
chuyển (qi,aj), và ô (i, j) là ô trống (hoặc ghi kí hiệu Ø) nếu (qi,aj) không xác định.
Cho bảng chuyển trạng thái, và chỉ rõ tập trạng thái kết thúc F, quy ước q0 là trạng
thái khởi đầu, ta sẽ hoàn toàn xác định được otomat A.
Bảng chuyển trạng thái của otomat A sẽ có dạng như sau:
76
Ký hiệu vào
Trạng
thái
…
a1
a2
an
q0
q1
…
…
…
…
…
(q0, a1) (q0, a2)
(q1, a1) (q1, a2)
(q2, a1) (q2, a2)
(q0, an)
(q1, an)
q2
(q2, an)
…
qm
…
…
…
(qm, a1) (qm, a2)
(qm, an)
Hình 3.2. Bảng chuyển trạng thái của otomat A
Biểu diễn otomat bằng đồ thị chuyển trạng thái
Cho otomat A = <Q, , , q0, F>. Hàm chuyển có thể cho bằng một đa đồ thị có
hướng, có khuyên G, được gọi là đồ thị chuyển trạng thái (hay đồ thị chuyển) của otomat
A. Tập đỉnh của G được gán nhãn bởi các phần tử thuộc Q, còn các cung được gán nhãn
bởi các phần tử thuộc , tức là nếu a và từ trạng thái q chuyển sang trạng thái p theo
công thức (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 là đỉnh ứng với trạng thái ban đầu q0. Các đỉnh sẽ
được khoanh bởi các vòng tròn, tại đỉnh xuất phát q0 có mũi tên đi vào, riêng đỉnh với
trạng thái kết thúc được phân biệt bởi vòng tròn đậm, hoặc hình vuông…
Việc cho đồ thị chuyển với các quy ước như trên là hoàn toàn xác định được
otomat A.
Thí dụ 3.1: Cho hai otomat hữu hạn đơn định:
. A1 = <{q0, q1, q2}, {a, b}, , q0, {q2}>,
Với (q0, a) = q0, (q0, b) = q1, (q1, a) = q0, (q1, b) = q2, (q2, a) = q2, (q2, b) = q2.
Ta có bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A1 được cho
trong hình 3.3 và 3.4:
Trạng
Ký hiệu vào
thái
a
b
q0
q1
q2
q0
q0
q2
q1
q2
q2
Hình 3.3. Bảng chuyển trạng thái của A1
77
a
b
a
b
q0
q1
q2
a
b
Hình 3.4. Đồ thị chuyển trạng thái của A1
Dãy trạng thái của otomat A1 trong quá trình đoán nhận xâu vào = ababbab là:
a
b
a
b
b
a
b
q0
q0
q1
q0
q1
q2
q2
q2 F.
Hình 3.5. Quá trình đoán nhận xâu = ababbab của A1
Như vậy, xâu được đoán nhận bởi otomat A1.
. A2 = <{q0, q1, q2, q3}, {0, 1}, , q0, {q0}>,
trong đó (q0, 0) = q2, (q0, 1) = q1, (q1, 0) = q3, (q1, 1) = q0, (q2, 0) = q0, (q2,
1) = q3, (q3, 0) = q1, (q3, 1) = q2.
Ta có bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A2 được cho
trong hình 3.6 và 3.7:
Trạng
thái
q0
q1
q2
Ký hiệu vào
0
1
q2
q3
q0
q1
q1
q0
q3
q2
q3
Hình 3.6. Bảng chuyển trạng thái của otomat A2
1
q1
q0
1
0
0
0
0
1
1
q3
q2
Hình 3.7. Đồ thị chuyển trạng thái của otomat A2
78
Dãy trạng thái của otomat A2 trong quá trình đoán nhận xâu vào = 1010100
được mô tả trong hình 3.8 dưới đây:
Hình 3.8. Quá trình đoán nhận xâu vào = 1010100
Như vậy, otomat A2 không chấp nhận xâu .
Ta có thể mô tả quá trình đoán nhận xâu vào của otomat hữu hạn đơn định đầy đủ
A bằng thuật toán mô phỏng sau:
Input :
. Một xâu , kết thúc bởi ký hiệu kết thúc file là eof.
. Một otomat hữu hạn đơn định đầy đủ A với trạng thái khởi đầu q0 và tập trạng
thái kết thúc là F.
Output:
. Trả lời “Đúng” nếu A đoán nhận xâu .
. Trả lời “Sai” nếu A không đoán nhận xâu .
Thuật toán:
Begin
S := q0;
C := ký hiệu đầu tiên của ;
While C < > eof do
begin
S:= (S, C);
C:= ký hiệu tiếp theo;
end;
if S in F return (True)
else return (False);
End.
79
3.1.3. Ngôn ngữ được đoán nhận bởi otomat đơn định
Để mô tả hình thức quá trình đoán nhận một từ (xâu vào), người ta đưa vào ánh xạ
mở rộng ’ từ Q×* vào Q như trong định nghĩa sau:
Định nghĩa 3.2
Cho otomat hữu hạn đơn định A = <Q, , , q0, F>. Mở rộng ’ của là một ánh
xạ từ Q×* vào Q được xác định như sau:
1. ’(q, ) = q, q Q,
2. ’(q, φa) = (’(q, φ), a), a , q Q, = φa * sao cho ’(q, φ) được
xác định.
Chú ý rằng, ánh xạ chỉ khác ánh xạ ’ khi ký hiệu vào là , hoặc là một xâu kí
hiệu vào , do điều kiện 2., trên Q×, ta có thể đồng nhất ’ với . Nếu không cần phân
biệt, từ đây về sau ta viết thay cho ’, và được hiểu là ánh xạ trên miền Q×, hiểu là
ánh xạ ’ trên miền Q×*.
Định nghĩa 3.3
Cho otomat hữu hạn đơn định A = <Q, , , q0, F>, và một xâu *. Ta nói
được đoán nhận bởi A nếu (q0, ) F. Tập hợp tất cả các từ được đoán nhận bởi
otomat A gọi là ngôn ngữ được đoán nhận bởi otomat A, và ký hiệu là T(A), vậy:
T(A) = { * | (q0, ) F}
Từ định nghĩa trên, ta thấy rằng trong đồ thị chuyển của A, xâu * được đoán
nhận bởi A khi và chỉ khi là xâu của các nhãn ứng với một đường đi từ đỉnh q0 đến
một trong các đỉnh kết thúc. Cụ thể, nếu = a1a2… ak thì đường đi là (q0, q1,…, qk) với
cung (qi-1, qi) có nhãn ai (với 1 i k) và qk F.
Như vậy, T(A) là tập hợp tất cả xâu ghi trên các đường đi từ q0 đến một đỉnh kết
thúc nào đó của otomat A.
Bổ đề 3.1
Cho otomat hữu hạn đơn định A = <Q, , , q0, F>. Khi đó 1, 2 *, q Q
sao cho (q, 12) xác định, ta có:
(q, 12) = ((q, 1), 2)
(1)
Chứng minh: Ta chứng minh đẳng thức trên bằng quy nạp theo độ dài của 2.
. Khi |2| = 1 hay 2 = a, a , ta có (q, 1a) = ((q, 1),a). Đẳng thức (1) đúng.
80
. Giả sử đẳng thức (1) đúng với mọi 2 có độ dài |2| n. Ta cần chứng minh nó
cũng đúng với 2 có độ dài |2| = n + 1. Đặt 2 = ’2a, với ’2 *, |’2| = n, a . Ta
có (q, 12) = (q, 1’2a) = ((q, 1’2), a) = (((q, 1), ’2), a) = ((q, 1),
’2a) = ((q, 1), 2).
Do đó đẳng thức (1) đúng với 2 có độ dài n + 1.
Bổ đề được chứng minh.
Chú ý:
1. Với otomat hữu hạn đơn định A = <Q, , , q0, F> bất kỳ, ta luôn có thể xây
dựng một otomat hữu hạn đơn định đầy đủ A’ tương đương với A.
Thật vậy, lấy S Q (do đó S F), đặt Q’= Q {S} và ’: Q’ x Q’ xác định
bởi: q Q, a , ’(q, a) = (q, a) nếu (q, a) được xác định, ’(q, a) = S nếu (q, a)
không được xác định và ’(S, a) = S. Khi đó A’ là otomat hữu hạn đơn định đầy đủ mà
T(A’) = T(A).
Ta thường chọn S = , và không cần bổ sung S vào Q.
2. Trên đồ thị chuyển một otomat đơn định và đầy đủ được thể hiện: với mỗi đỉnh
(gán nhãn là một trạng thái) đều có số cung đi ra khỏi đỉnh đó đúng bằng số ký hiệu của
bảng chữ cái, mỗi cung ra khác nhau được gán nhãn bằng một chữ cái khác nhau.
Chẳng hạn, các otomat A1 và A2 trong thí dụ 3.1 là các otomat đơn định và đầy đủ.
3.2. OTOMAT HỮU HẠN KHÔNG ĐƠN ĐỊNH
3.2.1. Định nghĩa otomat hữu hạn không đơn định
Định nghĩa 3.4
Otomat hữu hạn không đơn định (Nondeterministic Finite Automata-NFA) là
một bộ năm:
A = <Q, , , q0, F>
trong đó Q, , q0, F như trong định nghĩa của DFA, riêng hàm chuyển trạng thái là
một ánh xạ không đơn định : Q × 2Q, ở đây 2Q là ký hiệu tập tất cả các tập con của Q.
Ở đây ánh xạ là một hàm đa trị, cho kết quả là một tập trạng thái, tức là q Q,
a thì (q, a) = {p1, p2,… pk} Q (hàm không đơn định), vì vậy otomat A trong
định nghĩa trên đây được gọi là không đơn định.
Trong trường hợp (q, a) xác định q Q, a , ta nói otomat A là đầy đủ.
81
Nếu (q, a) = {p1, p2,…, pk} thì ta nói rằng otomat A ở trạng thái q gặp ký hiệu a
thì có thể chuyển đến một trong các trạng thái p1, p2,…, pk. Nếu (q, a) = {p} thì ở trạng
thái q gặp ký hiệu a, otomat A chỉ chuyển đến một trạng thái duy nhất p, trường hợp này
cũng giống như trong otomat hữu hạn đơn định. Như vậy, ta thấy rằng một otomat hữu
hạn đơn định cũng có thể coi là một otomat hữu hạn không đơn định đặc biệt, với kết
quả của hàm chuyển (q, a) là một tập chỉ gồm một trạng thái.
Nếu (q, a) không xác định (ta thường viết (q, a) = ) thì ở trạng thái q gặp ký
hiệu a, otomat A không thể chuyển đến trạng thái nào, otomat sẽ dừng, (tương tự như
với DFA).
Hoạt động của otomat hữu hạn không đơn định A = <Q, , , q0, F> khi cho xâu
vào = a1a2… an có thể được mô tả như sau:
Khi bắt đầu làm việc, otomat ở trạng thái khởi đầu q0 và đầu đọc đang nhìn vào ô
có ký hiệu a1. Từ trạng thái q0, dưới tác động của ký hiệu vào a1, (q0, a1) = {p1,…, pk},
otomat xác định trạng thái tiếp theo có thể là một trong các trạng thái p1,…, pk và đầu
đọc chuyển sang phải một ô, tức là nhìn vào ô có ký hiệu a2. Tiếp tục với mỗi pi (1 i
k) và ký hiệu tiếp theo là a2, các trạng thái tiếp theo có thể đến được là (p1,
a2)…(pk, a2). Quá trình đó sẽ tiếp tục cho tới khi gặp một trong các tình huống sau:
a). Otomat A đọc hết xâu vào và chuyển sang tập trạng thái Q’, khi đó có hai
khả năng:
(i) Nếu Q’F , ta nói rằng otomat A đoán nhận .
(ii) Nếu Q’ F = , ta nói rằng A không đoán nhận .
b). Hoặc ở bước i-1, có (qi-1, aj-1) = {p1,…, pk}= Q’, mà pi Q’, hàm chuyển
(qi , aj) không xác định, khi đó otomat A dừng, ta cũng nói A không đoán nhận xâu .
Chú ý rằng nếu A là otomat đầy đủ thì tình huống a). luôn xảy ra, tức là xâu
luôn được đọc hết, còn tình huống b). chỉ có thể xảy ra khi A là otomat không đầy đủ.
Một otomat hữu hạn không đơn định có thể biểu diễn dưới dạng bảng chuyển
hoặc đồ thị chuyển như trong trường hợp otomat hữu hạn đơn định. Nếu (q, a) = {p1,
p2,…, pk} thì trong đồ thị chuyển có k cung từ q sang p1,.., pk được ghi cùng một nhãn a.
Thí dụ 3.2: Cho otomat hữu hạn không đơn định:
A = <{q0, q1, q2, q3, q4}, {0, 1}, , q0, {q2, q4}>,
Với (q0,0) = {q0,q3}, (q0, 1) = {q0,q1}, (q1, 0) = , (q1, 1) = {q2}, (q2, 0) = {q2},
(q2, 1) = {q2}, (q3, 0) = {q4}, (q3,1) = , (q4, 0) = {q4}, (q4, 1) = {q4}.
82
Bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A cho trong hình
3.9 và 3.10:
Ký hiệu vào
Trạng
thái
a1
a2
q0
q1
q2
q3
q4
{q0, q3}
{q0, q1}
{q2}
{q2}
{q4}
{q4}
{q2}
{q4}
Hình 3.9. Bảng chuyển của otomat không đơn định A
Otomat A trên đây là không đơn định và không đầy đủ. Dựa vào bản chuyển trạng
thái, ta có thể xây dựng đồ thị chuyển trạng thái của A như sau:
0
0
1
1
1
1
q0
q1
q2
0
q3
0
1
0
q4
Hình 3.10. Đồ thị chuyển của otomat không đơn định A
Chú ý: Trên đồ thị chuyển một otomat không đơn định được thể hiện: tồn tại ít
nhất một đỉnh (gán nhãn là một trạng thái) mà có ít nhất hai cung ra khác nhau được gán
nhãn bằng cùng một chữ cái.
Chẳng hạn, trong đồ thị chuyển của otomat A trong hình 3.10, tại đỉnh q0, có hai
cung ra cùng ghi kí hiệu ‘0’, nên A là otomat không đơn định. Hơn nữa, A cũng là
otomat không đầy đủ.
Từ đồ thị chuyển, có thể thấy rằng otomat A trên đây cũng không phải là otomat
đầy đủ, vì có những đỉnh (trạng thái), từ đó có số cung đi ra ít hơn số ký hiệu trong bảng
chữ cái (tại đỉnh gán nhãn q1 và q3).
83
3.2.2 Ngôn ngữ được đoán nhận bởi otomat hữu hạn không đơn định
Định nghĩa 3.5
Cho otomat hữu hạn không đơn định A = <Q, , , q0, F>. Mở rộng của là ánh
xạ ’ từ tập Q× * vào 2Q được xác định như sau:
1) ’(q, ) = {q}, q Q,
*
’
2) ’(q, φa) =
, q Q, a , = φa sao cho (q, φ)
p (q,a)
được xác định.
Cũng như trường hợp otomat hữu hạn đơn định, ta có thể sử dụng ký hiệu thay
cho ’ , ký hiệu này được hiểu là ánh xạ trên miền Q × , và được hiểu là ánh xạ ’ trên
miền Q× *.
Thật vậy, trên miền Q×,ta có ’(q, a) = ’(q, a) =
= (q, a),
p
p (q,a)
'(p,)
=
p
(q,a)
q Q, a , tức là trên Q× thì ánh xạ ’ chính là ánh xạ .
Định nghĩa 3.6
Cho otomat hữu hạn không đơn định A = <Q, , , q0, F>, và một xâu *. Ta
nói được đoán nhận bởi A nếu (q0, ) F . Tập tất cả các từ được đoán nhận
bởi otomat A gọi là ngôn ngữ được đoán nhận bởi otomat A, và ký hiệu là T(A).
T(A) = { * | (q0, ) F }.
Thí dụ 3.3: Cho otomat hữu hạn không đơn định:
A = <{q0, q1, q2}, {a, b}, , q0, {q2}>,
trong đó (q0, a) = {q0}, (q0, b) = {q0, q1}, (q1, a) = {q1}, (q1, b) = {q1, q2},
(q2, a) = {q2}, (q2, b) = {q2}.
Bảng chuyển và đồ thị chuyển của otomat A được cho trong hình 3.11 và 3.12:
Ký hiệu vào
Trạng thái
a
b
q0
q1
q2
{q0}
{q1}
{q2}
{q0, q1}
{q1, q2}
{q2}
Hình 3.11. Bảng chuyển của otomat A trong thí dụ 3.3
84
a
a
a
b
b
q0
q1
q2
b
b
b
Hình 3.12. Đồ thị chuyển của otomat A trong thí dụ 3.3
Có thể kiểm tra được rằng từ = anbn T(A), tuy nhiên otomat A không đoán
nhận ngôn ngữ L = { anbn | n 1}. Ngôn ngữ được đoán nhận bởi otomat A là:
T(A) = {1b2b3 | 1, 2, 3 {a, b}*}.
3.2.3 Otomat hữu hạn với các bước chuyển rỗng
Xét otomat hữu hạn không đơn định A = <Q, , , q0, F> với các thành phần như
trong định nghĩa 3.4. Nếu hàm chuyển trạng thái được xác định trên miền Q x ( {}),
tức là biến thứ hai của hàm chuyển chấp nhận giá trị , và ta có (q, ) = {p1, p2,…
pk}. Nói các khác, khi đang ở trạng thái q, otomat A có thể chuyển sang một trong các
trạng thái p1, p2,… pk mà không cần đọc một ký hiệu nào. Một bước chuyển như vậy
được gọi là một bước chuyển” nhắm mắt” hay bước chuyển rỗng của otomat A, hay
một - chuyển (-move). Một bước chuyển rỗng từ trạng thái q sang trạng thái p được
biểu diễn trên đồ thị chuyển là một cung đi từ q đến p, trên đó có ghi nhãn là .
Như vậy, các otomat có -chuyển sẽ có hàm chuyển trạng thái là ánh xạ
: Q×({}) 2Q.
Dễ dàng thấy rằng, mọi otomat có -chuyển đều là các otomat không đơn định,
chẳng hạn xét thí dụ sau:
Thí dụ 3.4: Cho otomat A với đồ thị chuyển.
1
1
q1
0
q0
q2
q3
Hình 3.13. Đồ thị chuyển của otomat A trong thí dụ 3.4
Ta có A là một otomat hữu hạn với -chuyển (q1, ) = q3. Ta sẽ chứng tỏ rằng A
là một otomat không đơn định. Thật vậy:
85
Từ đồ thị chuyển, ta có: (q0, 1) = q1,
(i)
nhưng ta cũng có: (q0, 1) = (q0, 1) = ((q0, 1),) = (q1, ) = q3.
Từ (i) và (ii), ta có: (q0, 1) = {q1, q3}, vậy otomat A là không đơn định.
(ii)
Dễ thấy rằng, ngôn ngữ được đoán nhận bởi otomat A là: T(A) = {1, 110n | n ≥ 0}.
3.2.4. Các otomat tương đương
Đối với các otomat hữu hạn, người ta quan tâm đến các ngôn ngữ mà nó đoán
nhận, bất kể chúng là các otomat loại nào, đơn định hay không đơn định. Nếu hai
otomat hữu hạn cùng đoán nhận một ngôn ngữ thì ta nói chúng tương đương, Ta có định
nghĩa sau:
Định nghĩa 3.7
Hai otomat hữu hạn A = <Q, , , q0, F> và A’= <Q’, ’, ’, q’0, F’> được gọi là
tương đương nếu T(A) = T(A’).
Cho trước một otomat A, việc xác định các otomat tương đương thường nhằm làm
đơn giản otomat ban đầu nhờ việc loại bỏ các trạng thái không tham gia vào việc đoán
nhận ngôn ngữ, các trạng thái như vậy gọi là các “trạng thái chết” (dead states). Một
trạng thái p sẽ là trạng thái chết nếu không có một đường đi nào từ q0 đến một trạng thái
kết thúc mà đi qua p.
Thí dụ 3.5: Cho otomat hữu hạn: A = <{q0, q1, q2, q3, q4},{0, 1}, , q0, {q1, q2, q4}>,
với: (q0,0) = q0, (q0,1) = q1, (q1,0) = q3, (q1,1) = q2,
(q2,0) = q2, (q2,1) = q2, (q3,1) = q3,
(q4,0) = q2, (q4,1) = q3.
Đồ thị chuyển của A là:
0
0
1
1
1
1
q2
q0
q1
0
0
1
q3
q4
Hình 3.14. Đồ thị chuyển của otomat A trong thí dụ 3.5
86
Trước hết, ta nhận thấy rằng không có đường đi từ đỉnh q0 đến đỉnh kết thúc q4,
tức là sẽ không có từ nào được đoán nhận bởi A với đỉnh kết thúc q4. Ngoài ra, cũng
không có một đường đi nào từ q0 đến đỉnh một đỉnh kết thúc mà đi qua q3. Như vậy, các
trạng thái q3 và q4 sẽ không tham gia vào việc đoán nhận các từ, chúng là các trạng thái
chết. Trong đồ thị chuyển, ta có thể bỏ đi đỉnh q3 và q4 mà không ảnh hưởng đến tập từ
được đoán nhận bởi otomat A. Với việc bỏ đi các trạng thái chết q3 và q4, ta nhận được
otomat A’ tương đương với otomat A.
A’ = <{q0, q1, q2}, {0, 1}, , q0, {q1, q2}>,
trong đó (q0,0) = q0, (q0,1) = q1, (q1,1) = q2, (q2,0) = q2, (q2,1) = q2.
Đồ thị chuyển của A’ được cho trong hình 3.15 dưới đây:
0
0
1
1
q0
1
q1
q2
Hình 3.15. Đồ thị chuyển của otomat A’ trong thí dụ 3.5
Các đường đi từ q0 đến đỉnh kết thúc q1 ứng với các xâu 0n1, n 0. Các đường đi
từ q0 đến đỉnh kết thúc q2 ứng với các xâu 0n11, n 0, {0, 1}*. Vậy ngôn ngữ
được đoán nhận bởi các otomat trên là:
T(A) = T(A’) = {0n1, 0n11 | n 0, {0, 1}*}.
3.2.5. Vấn đề đơn định hóa otomat
Khi nghiên cứu các otomat và các ngôn ngữ hình thức, chúng ta thường gặp hai
bài toán cơ bản:
Bài toán phân tích: Cho một otomat hữu hạn A, hãy xác định ngôn ngữ được
đoán nhận bởi otomat này, tức là xác đinh tập T(A). Nói chung, việc xác định ngôn ngữ
được đoán nhận bởi otomat đơn định là dễ dàng hơn nhiều so với một otomat không
đơn định.
Bài toán tổng hợp: Cho một ngôn ngữ chính quy L, hãy xây dựng một otomat
hữu hạn đoán nhận L, tức là tìm otomat A để L = T(A). Bài toán này nói chung khó hơn
bài toán thứ nhất, với bài toán này, người ta thường xây dựng một otomat không đơn
định để đoán nhận ngôn ngữ L, vì việc này đơn giản hơn xây dựng một otomat đơn định
cũng đoán nhận L, sau đó, nếu cần thiết, tìm một otomat đơn định tương đương với
otomat vừa tìm được.
Như vậy, với cả hai bài toán trên, vấn đề tìm một otomat đơn định tương đương
87
với một otomat không đơn định cho trước là rất cần thiết, vì nó sẽ giúp cho việc giải
quyết cả hai bài toán trên trở nên đơn giản hơn. Vấn đề này được gọi là đơn định hóa
otomat, được phát biểu như sau:
Cho A = <Q, , , q0, F> là một otomat không đơn định, hãy xây dựng otomat
đơn định và đầy đủ M tương đương với otomat A, theo nghĩa cùng đoán nhận một ngôn
ngữ, tức là T(M) = T(A).
Việc xây dựng otomat M được thực hiện theo các thuật toán sau đây, được gọi là
thuật toán đơn định hóa otomat.
Thuật toán đơn định hóa 1
Input: Otomat hữu hạn không đơn định A = <Q, , , q0, F>
Output: Otomat hữu hạn đơn định M = <Q’, , ’, s0, F’> tương đương với
otomat A.
Phương pháp:
Bước 1:
Xây dựng hàm hai biến T: 2Q × 2Q thỏa mãn các điều kiện:
1. q Q, a thì T(q, a) = (q, a),
2. B Q mà B là tập trạng thái kết quả của hàm chuyển hoặc hàm T, mà
|B|> 1 thì:
T(B, a) =
pB
Bước 2:
Xác định tập trạng thái mới Q’ = {s0, s1,…, sk | k ≤ 2| Q | -1}:
1/. Đặt s0 = {q0}, s1 = {q1},… si = {qi}, q0, q1,…, qi Q,
2/. Đặt si+1 = B1, si+2 = B2,… với Bi là tập trạng thái kết quả của hàm chuyển ,
hoặc hàm T, | Bi | > 1.
3/. Nếu otomat A là không đầy đủ, đặt sk = và thêm vào hàm chuyển ’ các giá
trị ’(sk, a) = sk a để otomat M trở thành otomat đầy đủ.
4/. Trạng thái khởi đầu của otomat M là s0.
5/. Tập trạng thái kết thúc của otomat M là F’ = {s Q’ | s F ≠ }.
Bước 3 :
88
Xác định hàm chuyển ’: Q’ × Q’ của otomat M:
s Q’, a thì ’(s, a) = T(s, a)
Việc chứng minh T(A) = T(M) là khá dễ dàng, dành cho sinh viên như là bài tập.
Thí dụ 3.6: Cho otomat A = <{p0, p1, p2}, {a, b, c}, , p0, {p1, p2}> với hàm
chuyển cho bởi bảng sau:
a
b
c
p0
{p1}
{p1, p2}
{p2}
p1
p2
{p2}
{p1}
{p0, p2}
{p2}
{p1}
Hình 3.16. Bảng chuyển của otomat A trong thí dụ 3.6
Hãy xây dựng otomat M = <Q’, {a, b, c}, ’, s0, F’> đơn định và đầy đủ, tương
đương với otomat A.
1/. Xây dựng hàm T: 2Q × 2Q
T(p0, a) = {p1}, T(p0, b) = {p1, p2}, T(p0, c) = {p2},
T(p1, a) = {p2}, T(p1, b) = , T(p1, c) = {p0, p2},
T(p2, a) = {p1}, T(p2, b) = {p1}, T(p2, c) = {p2},
T({p1, p2}, a) = T(p1,a) T(p2,a)= {p2}{p1}={p1, p2}, T({p1, p2}, b) =
{p1} = {p1}, T({p1, p2}, c) = {p0, p2} {p2} = {p0, p2},
T({p0, p2}, a) = {p1}, T({p0, p2}, b) = {p1, p2}, T({p0, p2}, c) = {p2}
2/. Đặt s0 = {p0}, s1 = {p1}, s2 = {p2}, s3 = {p1, p2}, s4 = {p0, p2}, s5 = ta có tập
trạng thái mới là Q’ = {s0, s1, s2, s3, s4, s5}.
3/. Hàm chuyển mới ’: Q’ × Q’ được xác định bởi bảng sau:
’
a
b
c
s0
s1
s3
s2
s1
s2
s3
s4
s5
s2
s1
s3
s1
s5
s5
s1
s1
s3
s5
s4
s2
s4
s2
s5
Hình 3.17. Bảng chuyển của otomat đơn định M trong thí dụ 3.6
89
Trạng thái khởi đầu của M là s0, tập trạng thái kết thúc mới là: F’ = {s1, s2, s3, s4}.
Rõ ràng otomat M = <{s0, s1, s2, s3, s4, s5}, {a, b, c}, ’, s0, {s1, s2, s3, s4}> với
hàm chuyển ’ cho bởi bảng trên là otomat hữu hạn đơn định và đầy đủ. Có thể thấy
rằng otomat M là tương đương với otomat A.
Thuật toán đơn định hóa 2
Input: Otomat hữu hạn không đơn định A = <Q, , , q0, F>
Output: Otomat hữu hạn đơn định M = <Q’, , ’, s0, F’> tương đương với
otomat A.
Phương pháp:
Bước 1:
Đặt trạng thái khởi đầu của otomat đơn định M là trạng thái khởi đầu q0 của
otomat không đơn định A. Đặt Q’ = {[q0]}, và tiếp tục xác định các trạng thái khác của
M trong bước 2.
Bước 2:
Với mỗi ký hiệu vào a và với mỗi trạng thái [qi, qj,… qk] trong Q’ của M, xác
định giá trị hàm chuyển trạng thái ’ như sau:
1. ’([qi, qj, …qk], a ) = (qi, a) (qj, a) … (qk, a) = [ql, qm, …qn]
2. Bổ sung trạng thái mới [ql, qm,… qn] vào Q’ nhờ phép gán Q’: = Q’ {[ql,
qm,… qn]}
(có thể ký hiệu mỗi trạng thái [qi, qj, …qk] của Q’ bởi B1, B2,…).
3. Lặp lại bước 2 để xác định các bước chuyển trạng thái của hàm chuyển và bổ
sung các trạng thái mới cho M, cho đến khi không có trạng thái mới nào được bổ sung.
Bước 3:
Trạng thái B = [qi, qj,… qk] Q’ gọi là trạng thái kết thúc nếu ít nhất một trong
các trạng thái qi, qj,…qk là trạng thái kết thúc của A, tức là B F’ nếu và chỉ nếu {qi, qj,
…qk} F Ø. Nếu otomat A chấp nhận thì trạng thái khởi đầu [q0] đồng thời được
đặt là trạng thái kết thúc của M’.
Như vậy thuật toán đã xây dựng được otomat đơn định M’, đễ dàng thấy rằng
T(M’) = T(A).
Thí dụ 3.7: Cho otomat không đơn định: A = <{q0, q1}, {a, b}, , q0, {q1}>,
90
trong đó (q0, a) = {q0}, (q0, b) = {q0, q1}, (q1, a) = {q0, q1}, (q1, b) = .
Đồ thị chuyển của A là:
b
q0
q1
a
b
Hình 3.18. Đồ thị chuyển của otomat A trong thí dụ 3.7
Do A là otomat không đơn đinh nên việc xác định tập từ T(A) là khá khó khăn.
Trước hết ta sẽ xây dựng otomat đơn định M = <Q’, {a, b}, ’, t0, F’> tương
đương với A.
Theo thuật toán đơn định hóa 2, ta thực hiện các bước sau:
Bước 1: Đặt trạng thái khởi đầu của M là [q0], và Q’ = {[q0]}
Bước 2: Tìm các trạng thái mới của M, bằng cách xác đinh các bước chuyển trạng
thái với mỗi trạng thái đã có của Q’.
. Với [q0] Q’:
- với ký hiệu vào a: ’([q0], a) = (q0, a) = [q0] ,
- với ký hiệu vào b: ’([q0], b) = (q0, b) = [q0, q1],
- bổ sungtrạng thái mới: Q’ := Q’ {[q0, q1]}= {[q0], [q0, q1]}
. Tiếp tục xét với [q0, q1] Q’
- với ký hiệu vào a: ’([q0, q1], a) = (q0, a) (q1, a) = [q0, q1],
- với ký hiệu vào b: ’([q0, q1], b) = (q0, b) (q1, b) = [q0, q1],
Do không có trạng thái mới bổ sungvào Q’, kết thúc bươc 2.
Bước 3 : do [q0, q1] có chứa q1 là trạng thái kết thúc của A, nên [q0, q1] là trạng
thái kết thúc của otomat M
Như vậy, otomat M được xác định bởi :
. Q’ = { [q0], [q0, q1]}, với ký hiệu t0 = [q0] và t1 = [q0, q1], ta có Q’ = {t0, t1}, .
. Bảng chữ cái = {a, b},
. Trạng thái khởi đầu : t0
. Tập trạng thái kết thúc F’ = {t1},
91
. Hàm chuyển trạng thái ’ được xác định
’(t0, a) = t0, ’(t0, b) = t1, ’(t1, a) = t1, ’(t1, b) = t1.
Ta có bảng chuyển của M:
a
b
t1
t1
’
t0
t0
t1
t1
Hình 3.19. Bảng chuyển của otomat đơn định M trong thí dụ 3.7
Rõ ràng otomat M là đơn định và có đồ thị chuyển như sau:
a
a
b
t1
t0
b
Hình 3.20. Đồ thị chuyển của otomat M trong thí dụ 3.7
Việc xác định ngôn ngữ được đoán nhận bởi otomat M là khá dễ dàng:
T(A) = T(M) = {anb | n 0, {a, b}*}.
Nhận xét: Với thuật toán 1, việc xây dựng otomat đơn định M là khá dễ dàng, các
bước đều được chuẩn hóa, thuận lợi cho việc lập trình. Tuy nhiên thuật toán này có
nhược điểm là số trạng thái của M thường là khá lớn, cho nên sau khi tìm được M, cần
loại bỏ các trạng thái không tham gia quá trình đoán nhận ngôn ngữ (dead states), để
làm cho otomat đơn giản hơn.
Thuật toán 2 thường cho kết quả ngắn gọn hơn so với thuật toán 1, chỉ những
trạng thái thực sự tham gia vào quá trình đoán nhận ngôn ngữ mới được bổ sung vào tập
trạng thái mới Q’. Tuy nhiên, nhược điểm của thuật toán này là việc thực hiện cần phải
linh hoạt, các quy tắc không được chuẩn hóa, cho nên khó lập trình. Otomat M có thể
không phải là đầy đủ.
Thuật toán 2 phù hợp với việc đơn định hóa các otomat có số trạng thái không
lớn, có thể tính trực tiếp, không cần lập trình.
92
Tải về để xem bản đầy đủ
44 trang
28080
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Automat và ngôn ngữ hình thức - Chương 3: Otomat hữu hạn và ngôn ngữ chính quy", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_automat_va_ngon_ngu_hinh_thuc_chuong_3_otomat_huu.pdf
