Bài giảng Automata và ngôn ngữ hình thức - Chương 3: Automata hữu hạn và biểu thức chính quy

1 
Automata hữu hạn & 
Biểu thức chính quy 
Nội dung: 
• Khái niệm DFA & NFA 
• Sự tương đương giữa DFA & NFA 
• Biểu thức chính quy 
• Các tính chất của tập chính quy 
Chương 3: 
2 
Định nghĩa ôtômát (automata) 
Định nghĩa: là máy trừu tượng có cơ cấu và hoạt động 
đơn giản nhưng có khả năng đoán nhận ngôn ngữ 
• Con người phải lập trình sẵn cho máy một ‘lộ trình’ để thực hiện 
Bộ điều khiển 
INPUT 
OUTPUT 
BỘ NHỚ 
3 
Phân loại automata 
Automata đơn định (Deterministic Automata): 
• Mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện 
tại (hàm chuyển của automata là đơn trị) 
Automata không đơn định (Non-deterministic Automata): 
• Tại mỗi bước di chuyển, nó có vài khả năng để lựa chọn (hàm 
chuyển của automata là đa trị) 
4 
Phân loại FA 
FA 
(Finite Automata) 
DFA 
Deterministic 
Finite Automata 
NFA 
Nondeterministic 
Finite Automata 
Biểu thức 
chính quy 
5 
Start 
1 
1 
0 
0 
0 
0 1 
1 
a b 
c 
d 
q1 q0 
q3 q2 
Ví dụ: 
Input 
Bộ điều khiển 
1 0 1 0 0 1 1 0 
Q : tập hữu hạn các trạng thái (p, q) 
Σ : bộ chữ cái nhập (a, b  ; w, x, y ) 
δ : hàm chuyển, ánh xạ: Q x Σ → Q 
q0  Q : trạng thái bắt đầu. 
F  Q : tập các trạng thái kết thúc. 
M=(Q, Σ, δ, q0, F) 
Trạng thái bắt đầu 
Trạng thái kết thúc 
x 
Phép chuyển trên nhãn x 
Automata hữu hạn đơn định (DFA) 
6 
Mở rộng hàm chuyển trạng thái 
1. δ(q, ) = q 
2. δ(q, wa) = δ( δ(q,w), a) với  w, a 
Ngôn ngữ được chấp nhận: 
L(M) = { x | δ( q0, x )  F } 
Ngôn ngữ 
chính quy Ví dụ: chuỗi nhập w=110101 
• δ(q0, 1) = q1 
• δ(q0, 11) = δ(q1, 1) = q0 
• δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2 
• δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3 
• δ(q0, 11010) =  = δ(q3, 0) = q1 
• δ(q0, 110101) =  = δ(q1, 1) = q0  F 
7 
Giải thuật hình thức 
• Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ 
L(M) được chấp nhận bởi automata M. 
• Input: chuỗi nhập x$ 
• Output: câu trả lời ‘YES’ hoặc ‘NO’ 
• Giải thuật: 
q := q0 ; 
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} 
While c $ do 
 begin 
 q := δ(q, c); 
 c := nextchar ; 
 end 
If (q in F) then write("YES") else write("NO"); 
8 
Automata hữu hạn không đơn định (NFA) 
Nhận xét: 
• Ứng với một trạng thái và một ký tự nhập, có thể có 
không, một hoặc nhiều phép chuyển trạng thái. 
• DFA là một trường hợp đặc biệt của NFA 
Start 0 
1 
1 
0 
1 
0 
q0 q3 q4 
1 
0 
q1 
q2 
0 
1 
• Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001 
0 
0 
1 0 0 1 0 
1 0 0 1 
1 
q0 q0 q0 q0 q0 q0 
q3 q1 q3 q3 q1 
q4 q4 
9 
Định nghĩa NFA 
Chú ý: khái niệm δ(q, a) là tập hợp tất cả các trạng thái p 
sao cho có phép chuyển từ trạng thái q trên nhãn a. 
Hàm chuyển trạng thái mở rộng: 
• δ(q, ) = {q} 
• δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà pδ(r, a) } 
 = δ( δ(q,w), a) 
• δ(P, w) = qP δ(q, w) với P  Q 
Q : tập hữu hạn các trạng thái. 
Σ : bộ chữ cái nhập. 
δ : hàm chuyển ánh xạ Q x Σ → 2Q 
q0  Q : trạng thái bắt đầu. 
F  Q : tập các trạng thái kết thúc. 
M=(Q, Σ, δ, q0, F) 
10 
Ví dụ: xét chuỗi nhập w=01001 và NFA đã cho ở trên 
• M( {q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q2, q4} ) 
{q4} {q4} q4 
Ø {q4} q3 
{q2} {q2} q2 
{q2} Ø q1 
{q0,q1} {q0,q3} q0 
1 0 Trạng thái 
Input δ • δ(q0, 0) = {q0,q3} 
• δ(q0, 01) = δ( δ(q0, 0), 1) 
 = δ({q0, q3},1) = δ(q0, 1) 
 δ(q3, 1) = {q0, q1} 
• δ(q0, 010) = {q0, q3} 
• δ(q0, 0100) = {q0, q3, q4} 
• δ(q0, 01001) = {q0, q1, q4} 
Do q4  F nên w=01001  L(M) 
Ví dụ về NFA 
11 
Sự tương đương giữa DFA & NFA 
Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn 
tại một DFA chấp nhận L. 
Giả sử NFA M={Q, Σ, δ, q0, F} chấp nhận L 
Ta xây dựng DFA M’={Q’, Σ, δ’, q0’, F’} chấp nhận L 
• Q’ = 2Q . Một phần tử trong Q’ được ký hiệu là [q0, q1, , qi] với q0, q1, 
, qi  Q 
• q0’ = [q0] 
• F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc 
trong tập F của M 
• Hàm chuyển δ’([q1, q2,..., qi], a) = [p1, p2,..., pj] nếu và chỉ nếu δ({q1, 
q2,..., qi }, a) = {p1, p2,..., pj} 
12 
Ví dụ về sự tương đương giữa DFA & NFA 
Ví dụ: NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) với hàm chuyển 
δ(q0,0) = {q0, q1}, δ(q0,1) = {q1}, δ(q1,0) = , δ(q1,1) = {q0, q1} 
Ta sẽ xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q0], F’) 
• Q’ = {, [q0], [q1], [q0, q1]} 
• F’ = {[q1], [q0, q1]} 
• Hàm chuyển δ’ 
 δ’(, 0) = δ’(, 1) =  
 δ’([q0], 0) = [q0, q1] 
 δ’([q0], 1) = [q1] 
 δ’([q1], 0) =  
 δ’([q1], 1) = [q0, q1] 
 δ’([q0, q1], 0) = [q0, q1] 
 δ’([q0, q1], 1) = [q0, q1] 
13 
NFA với - dịch chuyển (NFA) 
Định nghĩa: NFA M(Q, Σ, δ, q0, F) 
• δ : hàm chuyển ánh xạ Q x (Σ  {}) → 2Q 
• Khái niệm δ(q, a) là tập hợp các trạng thái p sao cho có phép chuyển 
nhãn a từ q tới p, với a  (Σ  {}) 
q0 q1 q2 
 
0 1 2 
Start  
Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2* 
q0 q1 q2 
0, 1 
0 1 2 
Start 1, 2 
0, 1, 2 
14 
Mở rộng hàm chuyển trạng thái cho NFA 
Định nghĩa -CLOSURE: 
● -CLOSURE(q) = { p | có đường đi từ q tới p theo nhãn  } 
● -CLOSURE(P) = qP -CLOSURE(q) 
Hàm chuyển trạng thái mở rộng: mở rộng δ thành δ* 
• δ* : Q x Σ* → 2Q 
• δ*(q, w) = { p | có đường đi từ q tới p theo nhãn w, trên đường đi có thể 
chứa cạnh nhãn  } 
Ta có: 
• δ*(q, ) = -CLOSURE(q) 
• δ*(q,a) = -CLOSURE(δ(δ*(q, ),a)) 
• δ*(q, wa) = -CLOSURE( δ( δ*(q, w), a) ) 
 Cách khác: δ*(q, wa) = -CLOSURE(P) 
 với P = { p | r  δ*(q, w) và p  δ(r, a) } 
• δ*(R, w) = qR δ*(q, w) 
15 
Mở rộng hàm chuyển trạng thái cho NFA 
Ví dụ: 
q0 q1 q2 
 
0 1 2 
Start  
• δ*(q0, ) = -CLOSURE(q0) = {q0, q1, q2} 
• δ*(q0, 0) = -CLOSURE(δ(δ*(q0, ), 0)) 
 = -CLOSURE(δ({q0, q1, q2}, 0)) = -CLOSURE(δ(q0, 0)  
δ(q1, 0)  δ(q2, 0) ) = -CLOSURE( {q0}     ) 
 = -CLOSURE({q0}) = {q0, q1, q2} 
• δ*(q0, 01) = -CLOSURE(δ(δ*(q0, 0), 1)) 
 = -CLOSURE(δ({q0, q1, q2}, 1)) = -CLOSURE({q1}) 
 = {q1,q2} 
• δ*(q0, 012) = -CLOSURE(δ(δ*(q0, 01), 2)) 
 = -CLOSURE(δ({q1, q2}, 2)) = -CLOSURE({q2}) = {q2} 
• Do q2  F nên w  L(M) 
Xét chuỗi nhập w = 012 
16 
Giải thuật hình thức cho NFA 
Mục đích: mô phỏng hoạt động của NFA 
Input: chuỗi nhập x$ 
Output: câu trả lời ‘YES’ (x được chấp nhận) hoặc ‘NO’ 
Giải thuật: 
q := -CLOSURE (q0) ; 
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} 
While c $ do 
 begin 
 q := -CLOSURE (δ(q, c)); 
 c := nextchar ; 
 end 
If (q in F) then write("YES") else write("NO"); 
17 
Sự tương đương giữa NFA và NFA 
Định lý 2: nếu L được chấp nhận bởi một NFA có -dịch 
chuyển thì L cũng được chấp nhận bởi một NFA không có 
-dịch chuyển. 
Giả sử: NFA M(Q, Σ, δ, q0, F) chấp nhận L 
Ta xây dựng: NFA M’={Q, Σ, δ’, q0, F’} 
Với: 
• F’ = F  q0 nếu -CLOSURE(q0) chứa một trạng thái thuộc F. 
 Ngược lại, F’ = F 
• δ’(q, a) = δ*(q, a) 
18 
Ví dụ: 
Xây dựng NFA tương đương M’={Q, Σ, δ’, q0, F’} 
• Q = {q0, q1, q2} 
• Σ = {0, 1, 2} 
• Trạng thái bắt đầu: q0 
• F’ = {q0, q2} 
• Hàm chuyển δ’ 
{q2}   q2 
{q2} {q1, q2}  q1 
{q2} {q1, q2} {q0, q1, q2} q0 
2 1 0 Trạng thái 
Inputs δ’ 
q0 q1 q2 
0, 1 
0 1 2 
Start 1, 2 
0, 1, 2 
q0 q1 q2 
 
0 1 2 
Start  
Sự tương đương giữa NFA và NFA 
19 
Xây dựng DFA từ NFA() 
Ví dụ: xây dựng DFA tương đương với NFA sau: 
M = (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10}) 
a 
b 
 
 
 
 
  
 
 
2 3 
6 7 8 9 10 0 1 
4 5 
a b b Start 
Ta xây dựng DFA M’= (Q’, Σ, δ’, q0’, F’) tương đương M 
• Trạng thái bắt đầu: q0’ ↔ -CLOSURE(q0) 
• F’ = { p | trong ký hiệu của p có chứa ít nhất một trạng thái của F } 
• Xây dựng hàm chuyển δ’ 
20 
Giải thuật xây dựng hàm chuyển δ’ 
Giải thuật: 
T := -CLOSURE (q0) ; T chưa được đánh dấu ; 
Thêm T vào tập các trạng thái Q’ của DFA ; 
While Có một trạng thái T của DFA chưa được đánh dấu do 
 Begin 
 Đánh dấu T; { xét trạng thái T} 
 For Với mỗi ký hiệu nhập a do 
 begin 
 U:= -closure((T, a)) 
 If U không có trong tập trạng thái Q’ của DFA then 
 begin 
 Thêm U vào tập các trạng thái Q’ của DFA ; 
 Trạng thái U chưa được đánh dấu; 
 [T, a] := U;{[T, a] là phần tử của bảng chuyển DFA} 
 end; 
 end; 
 End; 
21 
Xây dựng DFA từ NFA() 
● -CLOSURE(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] = A 
● -CLOSURE(δ(A, a)) = -CLOSURE({3, 8}) = {1, 2, 3, 4, 6, 
7, 8} → B 
● -CLOSURE(δ(A, b)) = -CLOSURE({5}) = {1, 2, 4, 5, 6, 7} 
→ C 
● -CLOSURE(δ(B, a)) = -CLOSURE({3, 8}) → B 
● -CLOSURE(δ(B, b)) = -CLOSURE({5, 9}) = {1, 2, 4, 5, 6, 
7, 9} → D 
● -CLOSURE(δ(C, a)) = -CLOSURE({3, 8}) → B 
● -CLOSURE(δ(C, b)) = -CLOSURE({5}) = → C 
● -CLOSURE(δ(D, a)) = -CLOSURE({3, 8}) → B 
● -CLOSURE(δ(D, b)) = -CLOSURE({5,10}) = {1, 2, 4, 5, 
6, 7, 10} → E 
● -CLOSURE(δ(E, a)) = -CLOSURE({3, 8}) → B 
● -CLOSURE(δ(E, b)) = -CLOSURE({5}) = → C 
22 
• Bảng hàm chuyển 
E A 
a 
a 
a 
a 
a 
b 
b 
b 
b 
b 
B D 
C 
Start 
C B E 
E B D 
C B C 
D B B 
C B A 
b a 
Ký hiệu nhập 
Trạng thái 
• Ký hiệu bắt đầu: q0’ = A (↔ -CLOSURE(q0) ) 
• Tập trạng thái kết thúc: F’ = {E} (vì trong E có chứa trạng 
thái 10  F) 
Xây dựng DFA từ NFA() 
23 
Biểu thức chính quy (RE) 
Vài ví dụ: 
• 00 : là biểu thức chính quy biểu diễn tập {00} 
• (0+1)* : tập hợp tất cả các chuỗi số 0 và số 1, 
kể cả chuỗi rỗng = {, 0, 1, 00, 01, 10, 11, 010, 
011, 0010 ... } 
• (0+1)*011 : ký hiệu cho tất cả các chuỗi 0, 1 
tận cùng bởi 011 = {011, 0011, 1011, 00011, 
11011, ... } 
24 
Biểu thức chính quy (RE) 
• (0+1)*00(0+1)* : tập hợp tất cả các chuỗi 0,1 có 
ít nhất hai số 0 liên tiếp = {00, 000, 100, 0000, 
0001, 1000, 1001, 011001, ... } 
• (0+ )(1+10)* : tất cả các chuỗi không có hai số 0 
liên tiếp = {, 0, 01, 010, 1, 10, 01010, 0111, ... } 
• 0*1*2* : {, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, 
... } 
• 00*11*22* : tất cả các chuỗi trong tập 0*1*2* với 
ít nhất một ký hiệu 0, 1 và 2 ↔ viết gọn thành 
0+1+2+ 
25 
Biểu thức chính quy (RE) 
Định nghĩa: cho Σ là một bộ chữ cái. BTCQ trên Σ là các tập 
hợp mà chúng mô tả được định nghĩa đệ quy như sau: 
●  là BTCQ ký hiệu cho tập rỗng 
●  là BTCQ ký hiệu cho tập {} 
● a  Σ, a là BTCQ ký hiệu cho tập {a} 
● Nếu r và s là các BTCQ ký hiệu cho các tập hợp R và S thì (r + s), (rs) 
và ( r*) là các BTCQ ký hiệu cho các tập hợp R  S, RS và R* tương ứng 
Thứ tự ưu tiên: 
Phép bao đóng > Phép nối kết > Phép hợp 
Ví dụ: 
• Biểu thức ((0(1*)) + 1) có thể viết là 01*+1 
26 
Tính chất đại số của BTCQ 
Phép hợp: 
• r +  =  + r = r 
• r + r = r 
• r + s = s + r 
• (r + s) + t = r + (s + t) = r + s + t 
Phép nối kết: 
• r = r = r 
• r = r =  
• (r + s) t = rt + st 
• r (s + t) = rs + rt 
Phép bao đóng: 
• * =  
• * =  
• r*r* = r* 
• (r*)* = r* 
• r* =  + r + r2 +  + rk +  
• r* =  + r+ 
• ( + r)+ = ( + r)* = r* 
• r*r = r r* = r+ 
Tổng hợp: 
• (r* + s*)* = (r*s*)* = (r + s)* 
• (rs)*r = r(sr)* 
• (r*s)* r* = (r + s)* 
27 
Sự tương đương giữa NFA và BTCQ 
Định lý 3: nếu r là BTCQ thì tồn tại một NFA với -dịch 
chuyển chấp nhận L(r) 
Chứng minh: quy nạp theo số phép toán 
• Xét r không có phép toán nào 
Start 
q0 q0 q0 qf qf 
Start Start 
r =  r =  r = a 
a 
Các NFA cho các kết hợp đơn 
• Xét r có i phép toán: r = r1 + r2, r = r1r2 hoặc r = r1* 
 Xây dựng NFA M1 = (Q1, Σ1, δ1, q1, {f1}) và M2 = (Q2, Σ2, δ2, q2, {f2}) sao 
cho L(M1) = L(r1) và L(M2) = L(r2) 
 Xây dựng NFA M như sau: 
28 
Sự tương đương giữa NFA và BTCQ 
q1 f1 
f0 
M1 
q2 f2 
M2 
q0 
Start 
 
 
 
 
 
q1 
f1 M1 f0 q0 
 
 
 
Start 
• r = r1 + r2 
• r = r1r2 
• r = r1* 
q2 f2 M2 q1 f1 M1 
Start  
29 
Sự tương đương giữa NFA và BTCQ 
Ví dụ: xây dựng NFA chấp nhận BTCQ r = 01* + 1 
• r có dạng: r = r1 + r2 với r1 = 01* và r2 = 1 
• r1 có dạng r1 = r3r4 với r3 = 0 và r4 = 1* 
• r4 có dạng r4 = r5* với r5 = 1 
q1 q2 
1 Start 
r2 
q3 q4 
0 Start 
r3 
 
q5 q6 
1 Start q7 q8 
  
 r4 = r5* = 1* 
 
 
 
q7 q5 
1 
Start q3 q8 
  
q4 
0 
q6 
r1 = r3r4 = 01* 
 
 
 
q4 q7 
Start 
q9 q10 
 
 
q3 
0 q5 
q1 q2 
q6 q8 
1  
1 
 
  
r = r1 + r2 = 01* + 1 
q5 q6 
1 Start 
r5 
30 
Sự tương đương giữa DFA và BTCQ 
Định lý 4: Nếu L được chấp nhận bởi một DFA, thì L được 
ký hiệu bởi một BTCQ 
Chứng minh: 
• L được chấp nhận bởi DFA M({q1, q2,..., qn}, Σ, δ, q1, F) • Đặt Rkij = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y  x) thì l ≤ k} (hay Rkij là tập hợp tất cả các chuỗi làm cho automata đi từ trạng thái i đến trạng thái j mà không đi ngang qua trạng 
thái nào lớn hơn k) 
• Định nghĩa đệ quy của Rkij : 
Rkij = R
k-1
ik(R
k-1
kk)*R
k-1
kj  R
k-1
ij 
R0ij = 
{a | δ(qi, a) = qj}, nếu i ≠ j 
{a | δ(qi, a) = qj}  {}, nếu i = j 
31 
Sự tương đương giữa DFA và BTCQ 
• Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi Rkij đều tồn tại một 
biểu thức chính quy ký hiệu cho Rkij . 
 k = 0: R0ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc  
 Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại BTCQ rk-1lm sao 
cho L(rk-1lm) = R
k-1
lm 
 Vậy đối với Rkij ta có thể chọn BTCQ 
rkij = (r
k-1
ik)(r
k-1
kk)*(r
k-1
kj) + r
k-1
ij 
→ bổ đề đã được chứng minh 
● Ta có nhận xét: 
L(M) = qj F R
n
1j 
● Vậy L có thể được ký hiệu bằng BTCQ 
r = rn1j1 + r
n
1j2 +  + r
n
1jp 
 với F = {qj1, qj2, , qjp} 
32 
Sự tương đương giữa DFA và BTCQ 
Ví dụ: viết BTCQ cho DFA 
Ta cần viết biểu thức: 
r = r312 + r
3
13 
Ta có: 
• r312 = r
2
13(r
2
33)*r
2
32 + r
2
12 
• r313 = r
2
13(r
2
33)*r
2
33 + r
2
13 
1 
1 
q1 
q2 
q3 
0 
0 0, 1 
Start 
33 
Thay vào và rút gọn, ta có: 
r = 0*1((0 + 1)0*1)* ( + (0 + 1)(00)*) + 0(00)* 
 + (0 + 1)0*1   rk33 
(0 + 1)(00)* 0 + 1 0 + 1 rk32 
(0 + 1)(00)*0   rk31 
0*1 1 + 01 1 rk23 
(00)*  + 00  rk22 
0(00)* 0 0 rk21 
0*1 1 1 rk13 
0(00)* 0 0 rk12 
(00)*   rk11 
k = 2 k = 1 k = 0 
Sự tương đương giữa DFA và BTCQ 
34 
 Mối liên hệ giữa FA và BTCQ 
Sơ đồ liên hệ: 
DFA 
NFA 
NFA 
RE 
Định lý 4 Định lý 2 
Định lý 1 
Định lý 3