Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 3: Văn phạm chính quy và ôtômát hữu hạn - Nguyễn Thị Thùy Linh
Nội dung
Chương 3:
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
VĂN PHẠM CHÍNH QUY
VÀ
ÔTÔMÁT HỮU HẠN
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
2
Ôtômát hữu hạn đơn định – DFA
(Deterministic Finite Automata)
Input : w *
Mô tả phi hình thức:
0
1
1
0
0
1
1
1
1
Ô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ừ sức chứa vô hạn
Output : Yes, w L
No, w L
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 ô.
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ừ.
Bộ điều khiển
q
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.
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.
3
4
1
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.
Đị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.
5
6
Biểu diễn hàm chuyển trạng
Ví dụ 3.1: Xét Ôtômát hữu hạn đơn định M(,Q, ,q0,F). trong đó:
Có 3 cách biểu diễn hàm chuyển (hàm chuyển trạng thái):
= {0, 1}
Theo định nghĩa (qi,a)=qj
Theo bảng truyền
Q = {q0, q1, q2, q3}
F = {q0}
Hàm cho bởi ma trận sau:
Ký hiệu vào
Trạng thái
0
1
q0
q2
q1
q1
q2
q3
q3
q0
q1
q0
q3
q2
Theo đồ thị
8
7
2
Biểu đồ chuyển cho Ôtômát hữu hạn nói ở trên (Ví dụ 3.1) sẽ
như sau:
Để 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:
q1
1
Mỗi nút tương ứng với một trạng thái.
q1
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.
Bắt đầu
Đầu
q1
q0
q0
1
0
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.
0
0
0
1
q3
q2
1
a
p
q
10
9
Tính chất của hàm chuyển trạng
Định nghĩa tập đoán nhận bởi (M)
Ký hiệu T(M)
1. (q,)=q
T(M) = { w | w * , (q0,w) = qf F }
Ví dụ:
2. (q,wa)= ((q,w),a)
3. (q,aw)= ((q,a),w), w * và a
4. (q,xy)= ((q,x),y), x,y *
w1 = 1010
w2 = 11001001
W3 = 110101
11
12
3
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:
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)
110101 110101 110101 110101 110101 110101
q0
q1
q0 F
q2
q3
q1
q0
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.
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:
VD: Viết quá trình đoán nhận chuỗi x = 110101
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.
13
14
Ngôn ngữ đoán nhận (thừa nhận) bởi M
Tập các chuỗi được ôtômát thừa nhận
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:
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.
q00 q2
q01 q1
q10 q3
q11 q0
q20 q0
q21 q3
q30 q1
q31 q2
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.
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
15
16
4
Ôtômát hữu hạn không đơn định – NFA
(Nondeterministic Finite Automata)
Ôtômát hữu hạn không đơn định (tt)
Tập đoán nhận bởi Ôtômat
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.
T(M) = {w | w * và q0w * qf với qf F}.
Ngôn ngữ đoán nhận bởi M là:
Đị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:
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
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.
nhất một quá trình dẫn xuất q0w * qf với qf
F.
Hệ viết lại W = (V, P) ngầm định của M cũng có V = Q.
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:
17
18
Ôtômát hữu hạn không đơn định (tt)
Ôtômát hữu hạn không đơn định (tt)
0, 1
0
{q0, q3}
1
{q0, q1}
{q2}
{q2}
0, 1
Nếu xét tất cả các quá trình, ta có một “cây” như sau:
q0
q1
q2
q3
q4
Đầu
q0
q3
q4
q001001
q01001
q0001 q001 q01
q1001 q301 q31
q41
q0
q1
q4 F
0
0
1
{q2}
{q4}
{q4}
q31001
q1
1
0, 1
{q4}
Như vậy chuỗi 01001 đã thừa nhận bởi M.
q2
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}*}
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.
19
20
5
Sự tương đương giữa ÔHĐ và ÔHK
Sự tương đương giữa ÔHĐ và ÔHK (tt)
•
Mỗi phần tử trong Q’ được ký hiệu bởi tập hợp {q1, q2,
…, qk}, với q1, q2, …, q0 Q.
Trạng thái đầu q0’ = {q0}.
Theo định nghĩa mỗi ÔHĐ cũng là một ÔHK, cho nên:
L(ÔHĐ) L(ÔHK) (1)
Định lý 3.1: Nếu L một ngôn ngữ được đoán nhận bởi một
ÔHK, thì cũng có một ÔHĐ đoán nhận L.
•
B2: Hàm chuyển ’ của M’ được thành lập theo công thức:
Nói cách khác L(ÔHK) L(ÔHĐ) (2)
Giải thuật: Input: M = (, Q, , q0, F) là ÔHK đoán nhận L.
Output: M’ = (, Q’, ’, q0’, F’) là OHĐ sao cho L(M’)=L(M)
(qi , a)
’({q1, q2, …, qk}, a) =
B3: Vẽ đồ thị chuyển trạng thái
B1: Đặt M’ = (, Q’, ’, q0’, F’), trong đó:
B4: Kết luận M’ và chú thích rõ 5 phần của Ôtômát
•
•
Q’ = 2Q
Với cách thành lập M’ trên ta hoàn toàn CM được L(M) = L(M’) (Tham khảo
sách “Ngôn ngữ hình thức” – Nguyễn Văn Ba, trang 32).
F’ là tập mọi trạng thái trong Q’ có chứa một trạng thái cuối
nào đó của M.
21
22
Sự tương đương giữa ÔHĐ và ÔHK (tt)
Ví dụ 3.3: Cho M = ({0, 1}, {q0, q1, q2}, ,
q0, {q2}), là một ÔHK trong đó hàm chuyển
trạng thái như sau:
• Kết luận :
M’ =( , Q’, ’, {q0}, F’) là OHĐ cần tìm.
Trong đó:
=
(q0, 0) = {q0, q1}
(q0, 1) = {q1}
(q1, 0) = {q2}
(q1, 1) =
Q’ =
’ (vẽ đồ thị Chú ý: cắt bỏ các nhánh không xuất phát từ q0 hoặc
xuất phát từ q0 nhưng không kết thúc được)
(q2, 0) = {q2}
(q2, 1) = {q2}
Tìm OHĐ tương đương?
q0 là trạng thái bắt đầu
F’ =
23
24
6
Sự tương đương giữa ÔHĐ và ÔHK (tt)
Bổ đề 3.1:
Thực ra trong 2Q thường có nhiều phần tử
không thể truy đạt từ {q0}, nên chẳng cần đưa
chúng vào Q’. Vậy để lập Q’, ta nên truy xuất
từ {q0}, rồi từng bước thêm dần các trạng thái
mới, nếu các trạng thái này là kết quả của hàm
chuyển thái áp dụng lên các trạng thái đã có
trước đó.
Lớp các ngôn ngữ đoán nhận bởi Ôtômát hữu
hạn đơn định (hay không đơn định) là một, và
gọi là lớp các ngôn ngữ chính quy (viết tắt là
NNCQ).
NNCQ được sinh ra bởi VPCQ nên VPCQ có
mối quan hệ mật thiết với OH. Nghĩa là
L(G)=L(M)=L là NNCQ
25
26
Cho ôtômát hữu hạn đơn định xây dựng VPCQ
Văn phạm chính quy
Định lý 3.2: Nếu L là một NNCQ trên bộ chữ cái , thì tồn tại một VPCQ phải G sao cho L –
{} = L(G).
Định nghĩa VPCQ (nhắc lại):
Giải thuật: (xây xựng một VPCQ phải từ một ôtômát hữu hạn đơn định)
Input: L = L(M) với M = (, Q, , q0, F) là ÔHĐ.
Output:Ta thành lập văn phạm G = (T, V, P, S) sao cho L(G)=L \ {}
• Một văn phạm chính quy phải nếu tập luật sinh của nó dạng:
A wB | w, với w * và A, B .
Input
Output
• Một văn phạm chính quy trái nếu tập luật sinh của nó dạng:
A Bw |w, với w * và A, B .
• Các văn phạm chính quy phải và trái được gọi chung là văn
phạm chính quy (viết tắt là VPCQ).
M = (, Q, , q0, F)
G = (T, V, P, S)
T =
Q = {q0, q1, q2,….
}
V = {V0,V1,V2,…}
P=
• Ngôn ngữ được sinh ra bởi VPCQ gọi là NNCQ.
V0 aV1
V1 aVf | a
(q0, a) = q1
(q1, a) = qf F
a và q0,q1 Q
a T
q0
S là kí hiệu bắt đầu trong P
F Q
27
28
7
GIẢI
c
a
b
Ví dụ 3.4: Tìm văn phạm chính qui sinh ra ngôn ngữ L. Biết rằng
L là ngôn ngữ được đoán nhận bởi OH sau đây:
Start
q3
q1
q2
a
b
Văn phạm sinh ra ngôn ngữ L có dạng
G=(T,V,P,S)
M=(, Q,,q1,F)
xác định như đồ thị:
c
T={a,b,c}
a
b
={a,b,c}
Q={q1,q2,q3}
F={q3}
V={S,A,B,}
Start
q3
q1
q2
P={S aS | aA
a
b
A bA | bB | b
B cB | c}
q1 là trạng thái bắt đầu
S là kí hiệu bắt đầu trong tập luật sinh
29
30
Ví dụ 3.5: Cho ÔHĐ M với = {a, b}, Q = {q0, q1, q2, q3}, F =
{q2}. Hàm chuyển cho như sau:
Tìm một số quá trình đoán nhận của OH:
Xét w1 = aabbb
q0aabbb q1abbb q1bbb q2bb q2b q2 F w1 L(M)
Xét w2 = aaa
a
a
b
q1
q0aaa q1aa q1a q1 F w2 L(M)
Xét w3 = ba, thật vậy: q0ba q3a q3 F w3 L(M)
Xét w4 = aba,thật vậy:q0aba q1ba q2a q3 F w4 L(M)
w2, w3, w4 L(G) (theo bổ đề 3.1)
T(M)={ab,aab,aabbb,abb,aaab,abbbb,…}
Dễ thấy rằng ngôn ngữ do Ôtômát M đoán nhận là:
L(M) = {ambn | m, n > 0}
q0
q1
q2
q3
q1
q1
q3
q3
q3
q2
q2
q3
b
a
a
b
Đầu
q2
q0
b
q3
a,b
Biểu đồ chuyển của ÔHĐ
Tìm văn phạm G sinh ra ngôn ngữ L, sao cho L=L(M)
Tìm L? (Có chứng minh)
•
•
Tìm văn phạm G sinh ra ngôn ngữ L, sao cho L(G)=L(M)
SV tự làm!
Ngôn ngữ tìm được là ngôn ngữ gì?
31
32
8
Cho VPCQ xây dựng ôtômát hữu hạn không đơn định
Cho VPCQ xây dựng ôtômát hữu hạn không đơn định
Cách xây dựng hàm chuyển trạng thái
Input
Output
Định lý 3.3: Nếu G là một VPCQ
phải, thì L(G) là một ngôn ngữ chính
quy.
Mỗi sản xuất dạng Vi a1a2 … anVj thuộc P
Ta có hàm chuyển trạng (qi, a1a2a3…an) = qj
Đồ thị vẽ như sau:
G = (T, V, P, S)
M = (, Q, , q0, F)
T
=T
Giải thuật xây dựng một
ôtômát hữu hạn không đơn
định từ một VPCQ phải:
V = {V0,V1,V2…}
Q = {q0, q1, q2,…}
P=
Start
a1
a2
an
{V0 aV1
V1 a1a2a3…V2
V2 a}
….
(q0,a) = q1
(q1, a1a2a3…) = q2
(q2,a) = q3
qj
qi
Input: G = (T, V, P, S).
Output:Ta thành lập một
ÔHK M đoán nhận L(G) như
sau:
Mỗi sản xuất dạng Vi a1a2 … an thuộc P
Ta có hàm chuyển trạng (qi, a1a2a3…an) = qf F
Đồ thị vẽ như sau:
V0 là kí hiệu bắt
đầu trong P
q0 là trạng thái bắt đầu
M = (, Q, , q0, F)
F = {q3 } Q
Vẽ đồ thị
Start
a1
a2
an
Kết luận M?
….
qf
qi
34
33
(q0,a)=q1
Ví dụ 3.6: Xây dựng một Ôtômát hữu hạn chấp nhận ngôn
ngữ được sinh bởi văn phạm có tập luật sinh như sau:
(q1,ab)=q0
(q1,b)=q2 F
F = {q2}
S aA
A abS| b
q0 là trạng thái bắt đầu
Vẽ đồ thị chuyển trạng thái như sau:
Giải
Đặt M=(,Q, , q0,F) là OH cần tìm
Trong đó:
={a,b}
Q={q0,q1}
Start
b
a
q2
q0
b
q1
a
Xác định như sau:
35
36
9
Kết luận M=(,Q, , q0,F) là OH cần tìm
ÔHĐ không xuất phát lại
•
•
•
•
•
•
Trong đó:
•Định nghĩa: Một ÔHĐ là không xuất phát lại nếu
không tồn tại cặp (q, a) để cho (q, a) = q0 với q0 là
trạng thái đầu
={a,b}
Q={q0,q1,q2,q3}
Xác định như sau:
F = {q2}
•Bổ đề 3.2: Có giải thuật cho phép biến đổi một ÔHĐ
M đã cho thành một ÔHĐ không xuất phát lại M’ sao
cho L(M’) = L(M).
q0 là trạng thái bắt đầu
Giải thuật:
Start
b
a
q2
q0
b
q1
a
–Giả sử M = (, {q0, q1, …, qn}, , q0, F).
–Lập ÔHĐ M’ = (, Q {qn+1}, ’, q0, F’) trong đó:
q3
37
38
ÔHĐ không xuất phát lại
Ví dụ 3.7: Tìm OHĐ không xuất phát lại M’ tương đương với
OHĐ có xuất phát lại M sao cho L(M’)=L(M)
(q,a)
Nếu q Q và (q, a) q0
'(q,a)
qn1
Nếu q Q và (q, a) = q0
(M)
’(qn+1, a) = ’(q0, a)
Gợi ý
Nếu q0 không thuộc F
Nếu q0 F
}
F
OHĐ không xuất phát lại cần tìm sẽ có đồ thị chuyển trạng
F'
F {qn1
thái sau:
Kết luận M' (, Q {qn+1}, ’, q0, F’) , chú thích 5 phần?
Dễ thấy M’ thực hiện cùng các bước chuyển như M, trừ khi
M chuyển về q0 thì M’ chuyển sang qn+1, nhưng sau đó lại tiếp
tục bắt chước như M thường.
(M’)
40
39
10
Các tính chất đóng của lớp các NNCQ (tt)
Gọi M’=(, Q {qn+1}, ’, q0, F’) là OHĐ cần tìm
Trong đó:
Định lý 3.4: Nếu L và L’ là các NNCQ thì L L’ cũng là NNCQ.
Định lý 3.5: Nếu L * là một NNCQ, thì * - L cũng là NNCQ.
Định lý 3.6: Nếu L và L’ là các NNCQ thì L L’ cũng là NNCQ.
a
b
’
= {a,b}
q0
q1
q2
q3
q3
q2
q3
q1
q3
q1
Q = {q0, q1,q2,q3 }
F’ = {q0,q2,q3}
q0 là trạng thái bắt đầu
’ như đồ thị
Bổ đề 3.3: Cho L * và ’. Có một ÔH với bộ chữ vào
đoán nhận L khi và chỉ khi có một ÔH với bộ chữ vào ’
đoán nhận L. (Nói cách khác khái niệm NNCQ không tùy
thuộc vào bộ chữ).
Định lý 3.7: Nếu L và L’ đều là các NNCQ thì LL’ cũng là
NNCQ.
Định lý 3.8: Nếu L là NNCQ thì L* cũng là NNCQ.
41
42
BIỂU THỨC CHÍNH QUI
Định lý KLEENE
Cách khác để mô tả ngôn ngữ chính qui là dùng biểu
thức chính qui (BTCQ).
Một BTCQ là sự kết hợp:
Định lý: và {} là các NNCQ.
Định lý: Với mọi w *, thì {w} là NNCQ.
Hệ quả: Mọi tập con hữu hạn của * đều là NNCQ.
Các ký tự trong , mỗi ký tự có thể xuất hiện nhiều
lần,
Các toán tử: bao đóng (+,*), ghép, hợp
Các dấu ngoặc: ()
Hệ quả: Mọi ngôn ngữ tạo nên từ các ngôn ngữ hữu
hạn bằng cách áp dụng một số hữu hạn lần các phép
hợp, ghép tiếp và * đều là NNCQ.
VD:
Định lý KLEENE: Mọi NNCQ đều có thể nhận được từ
các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu
hạn lần các phép hợp, ghép tiếp và *.
Với ngôn ngữ L= {a}, ta có BTCQ là a
L={a,b}, ta có BTCQ là a+b
L={ab} {a}, ta có BTCQ là ab+a
L={a,b} . {a} , ta có BTCQ là (a+b)a
44
43
11
Biểu thức chính qui
Định nghĩa 1: Cho là một bộ chữ. Một biểu thức chính quy
(viết tắt là BTCQ) trên và tập hợp do nó định nghĩa được chỉ
định được định nghĩa một cách đệ quy như sau:
Biểu thức chính qui (tt)
Các toán tử ưu tiên trong BTCQ từ cao tới thấp:
(1) Bao đóng :
1. Các biểu thức chính qui nguyên tố gồm:
0+ : số 0 được lặp lại ít nhất 1 lần, nhiều nhất n lần.
0* : số 0 được lặp lại ít nhất 0 lần, nhiều nhất n lần
(2) Ghép : .
là một biểu thức chính quy biểu thị tập rỗng.
là một biểu thức chính quy biểu thị tập {}.
a thì a là một biểu thức chính quy biểu thị tập {a}.
(3) Hợp : +
2. Nếu r và s là các biểu thức chính quy, lần lượt chỉ định các
tập R và S, thì (r+s), (rs), và (r*) là các biểu thức chính quy, và
lần lượt biểu thị các tập R S, RS, và R*.
3. Một BTCQ nếu và chỉ nếu nó có thể được xây dựng từ các
biểu thức chính qui nguyên tố bởi áp dụng một số hữu hạn lần
các qui tắc trong mục 2.
Khi viết một BTCQ, ta có thể bỏ qua một số ngoặc
đơn, chẳng hạn, ((0(1*))+0) có thể viết thành 01* + 0
vẫn dễ hiểu.
Ta cũng có thể viết tắt biểu thức rr* bởi r+.
45
46
Biểu thức chính qui (tt)
Liên kết giữa ngôn ngữ với BTCQ
Biểu thức chính qui (tt)
00 là một biểu thức chính quy chỉ định tập L={00}
(0+1)* chỉ định tập mọi chuỗi 0 và 1
Tập hợp các chuỗi được chỉ định bởi một BTCQ r được ký hiệu bởi L(r). Để cho
tiện ta dùng r vừa để chỉ biểu thức chính quy, vừa để chỉ tập hợp do nó chỉ
định.
(1+10)* chỉ định tập mọi chuỗi 0 và 1, có con 1 ở đầu và không
có hai con 0 liên tiếp.
(0+)(1+10)* chỉ định tập mọi chuỗi 0 và 1 không chứa hai con 0
liên tiếp. Cách khác (1+01)*(0+ )
(0+1)*011 chỉ định tập mọi chuỗi 0, 1 kết thúc bởi 011.
Định nghĩa 2:
Ngôn ngữ L(r) được biểu thị bởi bất kỳ một BTCQ r nào, thì được định nghĩa
bởi các qui tắc sau:
1. là một biểu thức chính qui biểu thị tập rỗng.
2. là một biểu thức chính qui biểu thị tập {}.
3. a thì r = a là một biểu thức chính qui biểu thị tập
L(r) = {a}.
0*1*2* chỉ định tập mọi chuỗi gồm một số con 0, tiếp đến một số
con 1, rồi đến một số con 2.
00*11*22* chỉ định tập các chuỗi trong đó 0, 1, 2 đều có mặt.
Nếu r và s là các BTCQ thì:
4. L(r+s) = L (r) L(s)
5. L(r.s) = L(r) L(s)
6. L((r)) = L(r)
Biểu thức đó thường được viết tắt là 0+1+2+.
Ví dụ 3.8: Hãy xây dựng BTCQ xác định các chuỗi có chứa số 0
và 1 xen kẻ nhau.
7. L(r*) = (L(r))*
48
47
12
Biểu thức chính qui (tt)
Biểu thức chính qui (tt)
Các tính chất đại số của biểu thức chính qui:
Dễ dàng Giải thuật rằng, cho r, s, t là các biểu thức chính quy, thì ta có
các đẳng thức sau, trong đó r = s có nghĩa là L(r) = L(s).
Ví dụ 3.8: cho BTCQ r = a* . (a+b)
Tìm ngôn ngữ L(r) gồm tất cả các chuỗi được chỉ định
bởi r.
1. r + s = s + r
8. r = r =
9. r + = r
2. r + r = r
Giải
Ta có L(r) = L(a*. (a+b)) = L(a*) L(a+b)
= (L(a))* (L(a) L(b))
= {an | n 0} {a,b}
= {an+1, anb | n 0 }
10. * =
3. r + (s + t) = (r + s) + t
4. r(st) = (rs)t
11.(+r)* = r*
12. r + r* = r*
13.(r*)* = r*
5. r(s + t) = rs + rt
6. (r + s)t = rt + st
7. r = r =r
14.(r*s*)* = (r + s)*.
49
50
Biểu thức chính qui (tt)
Liên quan giữa BTCQ và OH
Ví dụ 3.9: Cho BTCQ r = (aa)* (bb)*b
Biểu thị cho tập hợp tất cả các chuỗi sao cho có chẳn con chữ a theo sau
là lẻ con chữ b. Đó là
L(r) = {a2n b2m+1 | n,m 0 }
Ví dụ 3.10: Cho = {0,1}. Hãy xác định BTCQ r sao cho L(r) = {w * |
w có ít nhất một cặp số 0 liên tiếp }
Bổ đề 3.4: Với mọi tập hữu hạn L *, đều tồn tại một một
BTCQ mà tập nó chỉ định là L.
Định lý 3.9: Một ngôn ngữ L được chỉ định bởi một BTCQ khi và
chỉ khi nó được đoán nhận bởi một Ôtômát hữu hạn.
Phân tích: mỗi chuỗi w chứa tổi thiểu 00, trước và sau nó là tùy ý 0, 1
điều được.
Ta đã biết một chuỗi tùy ý trên = {0,1} được biểu thị bởi BTCQ là (0+1)*
hoặc (1+0)* điều đúng.
Vậy BTCQ cần tìm là r = (0+1)*00(1+0)*
Ghi chú: Thông thường có vô số các BTCQ cho bất lỳ một ngôn ngữ nào.
Nên kết quả tìm BTCQ không phải là duy nhất.
51
52
13
Thuật toán Thompson
Thuật toán Thompson (tt)
Bài toán: Cho một biểu thức chính quy. Hãy xây dựng ôtômát
hữu hạn không đơn định đoán nhận ngôn ngữ chính quy từ
biểu thức chính quy đã cho.
Sau đó áp dụng luật 1, luật 2 để xây dựng các ôtômát
không đơn định M1, M2,…, Mk tương đương đoán nhận các
ngôn ngữ L(r1), L(r2), …, L(rk).
Thuật toán:
Cuối cùng áp dụng luật 3 để xây dựng ôtômát không đơn
Vào: Một biểu thức chính quy r trên tập .
định M đoán nhận ngôn ngữ L(r).
Ra: Một ôtômát hữu hạn không đơn định đoán nhận ngôn
ngữ L(r).
• Luật 1: BTCQ r=, ngôn ngữ biểu thị cho nó là
L(r) = {}. Xây dựng OH đoán nhận L(r) như sau:
Sau đây là thuật toán Thompson:
Trước hết tách biểu thức chính quy r thành các biểu thức
chính quy thành phần r1, r2,…rk.
Đầu
q0
qf
53
54
Thuật toán Thompson (tt)
Thuật toán Thompson (tt)
M(r)
• Luật 2: BTCQ r=a trên ={a}, ngôn ngữ do nó sinh
ra là L(r)= {a}. Xây dựng OH đoán nhận L(r) như sau:
Đầu
i
f
M(s)
Đầu
a
q0
qf
b. Đối với BTCQ (r).(s) thì OHK đoán nhận ngôn ngữ
L(r).L(s) như sau:
•
Luật 3: Giả sử M(r), M(s) là các ôtômát thành
phần tương ứng với các BTCQ s và r:
Đầu
M(r)
M(s)
a. Với BTCQ (r) (s) ta xây dựng OH đoán nhận
ngôn ngữ L(r) L(s) như sau:
i
f
55
55
56
14
Thuật toán Thompson (tt)
Bài tập: cho NNCQ xây dựng Ôtômát
Ví dụ 3.12: Xây dựng Ôtômát đoán nhận tất cả các chuỗi
trên = {a,b,0,1} sao cho kết thúc bởi ab
c. Đối với BTCQ (r)* thì OHK đoán nhận ngôn ngữ (L(r))*
như sau:
Ví dụ 3.13: Xây dựng Ôtômát đoán nhận tất cả các chuỗi
thuộc {0, 1}* sao cho có chứa chuỗi con 01 đâu đó.
Đầu
M(r)
i
f
Ví dụ 3.14: Xây dựng Ôtômát đoán nhận ngôn ngữ
L={aabna | n 0}
Ví dụ 3.11: Xây dựng NFA từ biểu thức chính quy: 01*+1
58
57
15
15 trang
16540
Free
Bạn đang xem tài liệu "Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 3: Văn phạm chính quy và ôtômát hữu hạn - Nguyễn Thị Thùy Linh", để 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:
- bai_giang_otomat_va_ngon_ngu_hinh_thuc_chuong_3_van_pham_chi.pdf
