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
Phân loại FA
FA
(Finite Automata)
DFA
Deterministic
Finite Automata
NFA
Nondeterministic
Finite Automata
Biểu thức
chính quy
3
Start
1
1
0
0

x
Phép chuyển trên nhãn x
Automata hữu hạn đơn định (DFA)
4
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 | δ( q
0
, x ) ∈ F }
Ngôn ngữ
chính quy
Ví dụ: chuỗi nhập w=110101
•
δ(q
0
, 1) = q
1
•
δ(q
0
, 11) = δ(q
1
, 1) = q
0
•
δ(q
0
, 110) = δ(q

∈ F
5
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 := q
0
;
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");
6
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

q
0
q
0
q
0
q
0
q
0
q
3
q
1
q
3
q
3
q
1
q
4
q
4
7
Đị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
4
}, {0, 1}, δ, q
0
, {q
2
, q
4
} )
{q
4
}{q
4
}q
4
Ø{q
4
}q
3
{q
2
}{q
2
}q
2
{q
2
}Øq
1
{q

0
, 1)
∪ δ(q
3
, 1) = {q
0
, q
1
}
•
δ(q
0
, 010) = {q
0
, q
3
}
•
δ(q
0
, 0100) = {q
0
, q
3
, q
4
}
•
δ(q
0

i
] với q
0
, q
1
, …, q
i
∈ Q
•
q
0
’ = [q
0
]
•
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 δ’([q
1
, q
2
, , q
i
], a) = [p
1
, p
2
, , p
j

1
}, δ(q
0
,1) = {q
1
}, δ(q
1
,0) = ∅, δ(q
1
,1) = {q
0
, q
1
}
Ta sẽ xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q
0
], F’)
•
Q’ = {∅, [q
0
], [q
1
], [q
0
, q
1
]}
•
F’ = {[q
1

], 1) = [q
0
, q
1
]

δ’([q
0
, q
1
], 0) = [q
0
, q
1
]

δ’([q
0
, q
1
], 1) = [q
0
, q
1
]
11
NFA với ε- dịch chuyển (NFAε)
Định nghĩa: NFAε M(Q, Σ, δ, q
0
, F)

0, 1
0
1
2
Start
1, 2
0, 1, 2
12
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 Σ* → 2
Q
•
δ*(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
1
, q
2
}
•
δ*(q
0
, 0) = ε-CLOSURE(δ(δ*(q
0
, ε), 0))
= ε-CLOSURE(δ({q
0
, q
1
, q
2
}, 0)) = ε-CLOSURE(δ(q
0
, 0) ∪
δ(q
1
, 0) ∪ δ(q
2
, 0) ) = ε-CLOSURE( {q
0
} ∪ ∅ ∪ ∅ )
= ε-CLOSURE({q
0
}) = {q

0
, 01), 2))
= ε-CLOSURE(δ({q
1
, q
2
}, 2)) = ε-CLOSURE({q
2
}) = {q
2
}
•
Do q
2
∈ F nên w ∈ L(M)
14
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 (q
0
) ;
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

, q
1
, q
2
}
•
Σ = {0, 1, 2}
•
Trạng thái bắt đầu: q
0
•
F’ = {q
0
, q
2
}
•
Hàm chuyển δ’
{q
2
}∅∅q
2
{q
2
}{q
1
, q
2
}∅q
1

0
q
1
q
2
ε
0
1
2
Start
ε
Sự tương đương giữa NFAε và NFA
17
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

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;
19
Xây dựng DFA từ NFA(ε)
●
ε-CLOSURE(q
0
) = {0, 1, 2, 4, 7} → q
0
’ = [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

CBC
DBB
CBA
ba
Ký hiệu nhập
Trạng thái
•
Ký hiệu bắt đầu: q
0
’ = A (↔ ε-CLOSURE(q
0
) )
•
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(ε)
21
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, }
•
(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,

Ví dụ:
•
Biểu thức ((0(1*)) + 1) có thể viết là 01*+1
23
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*

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
q
0
q
0
q
0
q
f
q
f
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 = r
1
+ r
2
, r = r
1
r
2
hoặc r = r

) = L(r
1
) và L(M
2
) = L(r
2
)

Xây dựng NFAε M như sau:
25
Sự tương đương giữa NFAε và BTCQ
q
1
f1
f
0
M
1
q
2
f
2
M
2
q
0
Start
ε
ε
ε

q
2
f
2
M
2
q
1
f
1
M
1
Start ε