Chương 3:

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

1


Đị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

INPUT

Bộ điều khiển

OUTPUT

Nondeterministic
Finite Automata

Biểu thức
chính quy
4


Automata hữu hạn đơn định (DFA)
Ví dụ:

c

Input

1
Start

0 1 1 0 0 1 0 1

1 q1

q0
0

0

a

Bộ điều khiển



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 }

Ví dụ: chuỗi nhập w=110101
•
•
•
•
•
•

Ngôn ngữ
chính quy

δ(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
6


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ữ


q4

1
q1
1

q0

0

q0
0

0
1

q0
1

q3
q2

1

0

q0
0


q4

8


Định nghĩa NFA

M=(Q, Σ, δ, q0, F)

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.

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
9


Ví dụ về NFA
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}

• δ(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)
10


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
•
•

 δ’([q0, q1], 1) = [q0, q1]
12


NFA với - dịch chuyển (NFA)
Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2*
0
Start
q0

1
0, 1

q1

2
1, 2

q2

0, 1, 2

0
Start
q0

1


q1

δ*(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)

14


Mở rộng hàm chuyển trạng thái cho NFA
0

Ví dụ:

•
•

•



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");

16


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 = {q0, q1, q2}
Σ = {0, 1, 2}
Trạng thái bắt đầu: q0
F’ = {q0, q2}
Hàm chuyển δ’
0

Start

q0

1
0, 1

q1
0, 1, 2

1, 2

δ’
Trạng thái

Inputs
0

2

q0

q2




0

3



1


6


4

b

a
7

b
8

b
9

10


[T, a] := U;{[T, a] là phần tử của bảng chuyển DFA}
end;
end;
End;
20


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


D

C

B

C

D

B

E

E

B

C

b
C
b
Start
A

a

a

11011, ... }
23


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+
24


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)