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

BỘ NHỚ

2

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

3

Phân loại FA

DFA Deterministic Finite Automata

FA

(Finite Automata)

NFA Nondeterministic Finite Automata

Biểu thức chính quy

4

Automata hữu hạn đơn định (DFA)

Ví dụ:

c

Input

10100110

1

Start

q1

q0

1

0

0

Bộ điều khiển

a

b

Trạng thái bắt đầu

0

0

1

Trạng thái kết thúc

q2

q3

1

x

d

Phép chuyển trên nhãn x

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

5

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 (cid:0) F (cid:0)

Q : trạng thái bắt đầu. Q : tập các trạng thái kết thúc.

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

1. δ(q, (cid:0) ) = q 2. δ(q, wa) = δ( δ(q,w), a) với (cid:0)

w, a

Ngôn ngữ được chấp nhận:

F }

L(M) = { x | δ( q0, x ) (cid:0)

Ngôn ngữ chính quy

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

F

6

• δ(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 (cid:0)

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

7

Automata hữu hạn không đơn định (NFA)

• Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001

1 0

1 0

Start

0

0

q3

q0

q4

1

0

1

0

0

1

q1

q0

q0

q0

q0

q0

q0

1

0

1

0

1

0

q3

q1

q3

q3

q1

q2

0

1

q4

q4

0 1

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.

8

• DFA là một trường hợp đặc biệt của NFA

Đị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 (cid:0) F (cid:0)

Q : trạng thái bắt đầu. 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, (cid:0) ) = {q} • δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà p(cid:0) δ(r, a) }

= δ( δ(q,w), a)

Q

• δ(P, w) = (cid:0)

q(cid:0) P δ(q, w) với (cid:0) P (cid:0)

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} )

δ

Input

• δ(q0, 0) = {q0,q3} • δ(q0, 01) = δ( δ(q0, 0), 1) = δ({q0, q3},1) = δ(q0, 1)

Trạng thái q0 q1 q2 q3 q4

0 {q0,q3} Ø {q2} {q4} {q4}

1 {q0,q1} {q2} {q2} Ø {q4}

δ(q3, 1) = {q0, q1} • δ(q0, 010) = {q0, q3} • δ(q0, 0100) = {q0, q3, q4} • δ(q0, 01001) = {q0, q1, q4}

(cid:0)

(cid:0)

F nên w=01001 (cid:0)

L(M)

Do q4

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

• Q’ = 2Q . Một phần tử trong Q’ được ký hiệu là [q0, q1, …, qi] với q0, q1, …,

Q

qi (cid:0)

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

11

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) = (cid:0)

, δ(q1,1) = {q0, q1}

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

, [q0], [q1], [q0, q1]}

• Q’ = {(cid:0) • F’ = {[q1], [q0, q1]} • Hàm chuyển δ’

, 1) = (cid:0)

, 0) = δ’((cid:0)

12

 δ’((cid:0)  δ’([q0], 0) = [q0, q1]  δ’([q0], 1) = [q1]  δ’([q1], 0) = (cid:0)  δ’([q1], 1) = [q0, q1]  δ’([q0, q1], 0) = [q0, q1]  δ’([q0, q1], 1) = [q0, q1]

NFA với (cid:0) - dịch chuyển (NFA(cid:0) )

Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2*

0 1 2

Start 0, 1 1, 2 q0 q1 q2

0

1

2

Start

0, 1, 2

(cid:0) (cid:0)

q0

q1

q2

Định nghĩa: NFA(cid:0) M(Q, Σ, δ, q0, F)

{(cid:0) }) → 2Q

13

• δ : hàm chuyển ánh xạ Q x (Σ (cid:0) • 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 {(cid:0) })

nhãn a từ q tới p, với a (cid:0)

(Σ (cid:0)

Mở rộng hàm chuyển trạng thái cho NFA(cid:0) Định nghĩa (cid:0) -CLOSURE: ● (cid:0) -CLOSURE(q) = { p | có đường đi từ q tới p theo nhãn (cid:0) }

● (cid:0) -CLOSURE(P) = (cid:0)

q(cid:0) P (cid:0) -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 (cid:0) }

Ta có:

• δ*(q, (cid:0) ) = (cid:0) -CLOSURE(q) • δ*(q,a) = (cid:0) -CLOSURE(δ(δ*(q, (cid:0) ),a)) • δ*(q, wa) = (cid:0) -CLOSURE( δ( δ*(q, w), a) ) Cách khác: δ*(q, wa) = (cid:0) -CLOSURE(P) với P = { p | r (cid:0) δ(r, a) }

δ*(q, w) và p (cid:0)

• δ*(R, w) = (cid:0)

14

q(cid:0) R δ*(q, w)

Mở rộng hàm chuyển trạng thái cho NFA(cid:0)

0

1

2

Start

(cid:0) (cid:0)

Ví dụ:

q0

q1

q2

Xét chuỗi nhập w = 012

• δ*(q0, (cid:0) ) = (cid:0) -CLOSURE(q0) = {q0, q1, q2} • δ*(q0, 0) = (cid:0) -CLOSURE(δ(δ*(q0, (cid:0) ), 0))

)

(cid:0)

(cid:0)

(cid:0)

δ(q2, 0) ) = (cid:0) -CLOSURE( {q0} (cid:0)

= (cid:0) -CLOSURE(δ({q0, q1, q2}, 0)) = (cid:0) -CLOSURE(δ(q0, 0) (cid:0) δ(q1, 0) (cid:0) = (cid:0) -CLOSURE({q0}) = {q0, q1, q2}

• δ*(q0, 01) = (cid:0) -CLOSURE(δ(δ*(q0, 0), 1))

= (cid:0) -CLOSURE(δ({q0, q1, q2}, 1)) = (cid:0) -CLOSURE({q1}) = {q1,q2}

• δ*(q0, 012) = (cid:0) -CLOSURE(δ(δ*(q0, 01), 2))

15

= (cid:0) -CLOSURE(δ({q1, q2}, 2)) = (cid:0) -CLOSURE({q2}) = {q2}

F nên w (cid:0)

L(M)

• Do q2 (cid:0)

Giải thuật hình thức cho NFA(cid:0)

Mục đích: mô phỏng hoạt động của NFA(cid:0) 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 := (cid:0) -CLOSURE (q0) ; c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} While c <> $ do

begin

q := (cid:0) -CLOSURE (δ(q, c)); c := nextchar ;

end

If (q in F) then write("YES") else write("NO");

16

Sự tương đương giữa NFA(cid:0) và NFA

Định lý 2: nếu L được chấp nhận bởi một NFA có (cid:0) -dịch

chuyển thì L cũng được chấp nhận bởi một NFA không có (cid:0) -dịch chuyển.

Giả sử: NFA(cid:0) M(Q, Σ, δ, q0, F) chấp nhận L Ta xây dựng: NFA M’={Q, Σ, δ’, q0, F’} Với:

• F’ = F (cid:0)

q0 nếu (cid:0) -CLOSURE(q0) chứa một trạng thái thuộc F.

Ngược lại, F’ = F • δ’(q, a) = δ*(q, a)

17

Sự tương đương giữa NFA(cid:0) và NFA

0 1 2

Start (cid:0) (cid:0)

Ví dụ:

Xây dựng NFA tương đương M’={Q, Σ, δ’, q0, F’}

δ’

Inputs

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

q0 q1 q2

0 {q0, q1, q2}

0 1 2

1 {q1, q2} {q1, q2}

Start 0, 1 1, 2 (cid:0) q0 q2 q1

Trạng thái q0 q1 q2

2 {q2} {q2} {q2}

18

(cid:0) (cid:0) 0, 1, 2

Xây dựng DFA từ NFA((cid:0) )

Ví dụ: xây dựng DFA tương đương với NFA(cid:0) sau: M = (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10})

(cid:0)

a

3 2 (cid:0) (cid:0) (cid:0) (cid:0) a b b Start 0 6 7 8 9 1 10 (cid:0) (cid:0) b 5 4

Ta xây dựng DFA M’= (Q’, Σ, δ’, q0’, F’) tương đương M

• Trạng thái bắt đầu: q0’ ↔ (cid:0) -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 δ’

19

(cid:0)

Giải thuật xây dựng hàm chuyển δ’

Giải thuật:

T := (cid:0) -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 ;

20

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:= (cid:0) -closure((cid:0) (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; (cid:0) [T, a] := U;{(cid:0) [T, a] là phần tử của bảng chuyển DFA} end; end; End;

Xây dựng DFA từ NFA((cid:0) )

● (cid:0) -CLOSURE(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] = A ● (cid:0) -CLOSURE(δ(A, a)) = (cid:0) -CLOSURE({3, 8}) = {1, 2, 3, 4, 6,

7, 8} → B

● (cid:0) -CLOSURE(δ(A, b)) = (cid:0) -CLOSURE({5}) = {1, 2, 4, 5, 6, 7}

→ C

● (cid:0) -CLOSURE(δ(B, a)) = (cid:0) -CLOSURE({3, 8}) → B ● (cid:0) -CLOSURE(δ(B, b)) = (cid:0) -CLOSURE({5, 9}) = {1, 2, 4, 5, 6,

7, 9} → D

● (cid:0) -CLOSURE(δ(C, a)) = (cid:0) -CLOSURE({3, 8}) → B ● (cid:0) -CLOSURE(δ(C, b)) = (cid:0) -CLOSURE({5}) = → C ● (cid:0) -CLOSURE(δ(D, a)) = (cid:0) -CLOSURE({3, 8}) → B ● (cid:0) -CLOSURE(δ(D, b)) = (cid:0) -CLOSURE({5,10}) = {1, 2, 4, 5,

6, 7, 10} → E

21

● (cid:0) -CLOSURE(δ(E, a)) = (cid:0) -CLOSURE({3, 8}) → B ● (cid:0) -CLOSURE(δ(E, b)) = (cid:0) -CLOSURE({5}) = → C

Xây dựng DFA từ NFA((cid:0) )

• Bảng hàm chuyển

Ký hiệu nhập b Trạng thái a b C

A B C a b b

• Ký hiệu bắt đầu: q0’ = A (↔ (cid:0) -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 (cid:0)

B B D Start a b B A D E C B C b a a D B E a E B C

F)

22

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 = {(cid:0) , 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, ... }

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+ (cid:0) )(1+10)* : tất cả các chuỗi không có hai số 0 liên tiếp = {(cid:0) , 0, 01, 010, 1, 10, 01010, 0111, ... }

• 0*1*2* : {(cid:0) , 0, 1, 2, 01, 02, 12, 012, 0012,

0112, ... }

24

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

Biểu thức chính quy (RE)

là BTCQ ký hiệu cho tập rỗng

Σ, a là BTCQ ký hiệu cho tập {a}

Đị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: ● (cid:0) ● (cid:0) là BTCQ ký hiệu cho tập {(cid:0) } ● (cid:0) a (cid:0) ● 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)

S, RS và R* tương

và ( r*) là các BTCQ ký hiệu cho các tập hợp R (cid:0) ứ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

25

Tính chất đại số của BTCQ

+ r = r

Phép nối kết: r(cid:0) = (cid:0) r = r • r = (cid:0) = (cid:0) r(cid:0) • • (r + s) t = rt + st • r (s + t) = rs + rt

Phép hợp: • • • •

r + (cid:0) = (cid:0) r + r = r r + s = s + r (r + s) + t = r + (s + t) = r + s + t

(cid:0)

Tổng hợp: • • •

(r* + s*)* = (r*s*)* = (r + s)* (rs)*r = r(sr)* (r*s)* r* = (r + s)*

Phép bao đóng: • • • • • • • •

(cid:0) * = (cid:0) * = (cid:0) r*r* = r* (r*)* = r* r* = (cid:0) + r + r2 + … + rk + … r* = (cid:0) + r+ ((cid:0) + r)+ = ((cid:0) + r)* = r* r*r = r r* = r+

26

Sự tương đương giữa NFA(cid:0)

và BTCQ

Định lý 3: nếu r là BTCQ thì tồn tại một NFA với (cid:0) -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 Start Start a q0 qf qf q0 q0

r = (cid:0) r = (cid:0) r = a

• Xét r có i phép toán: r = r1 + r2, r = r1r2 hoặc r = r1*

 Xây dựng NFA(cid:0) 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(cid:0) M như sau:

27

Các NFA(cid:0) cho các kết hợp đơn

Sự tương đương giữa NFA(cid:0)

và BTCQ

• r = r1 + r2

(cid:0) (cid:0) M1 f1 q1 Start

q0 f0

(cid:0) (cid:0) M2 q2 f2

• r = r1r2

(cid:0) Start M1 M2 q1 f1 q2 f2

(cid:0)

• r = r1*

(cid:0) (cid:0) Start M1 q0 q1 f1 f0

28

(cid:0)

Sự tương đương giữa NFA(cid:0)

và BTCQ

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

(cid:0)

(cid:0) (cid:0) 1 1

Ví dụ: xây dựng NFA(cid:0) chấp nhận BTCQ r = 01* + 1 • • • Start

Start q7 q8 q5 q6 q1 q2

(cid:0)

r4 = r5* = 1*

(cid:0)

r2 0

Start q3 q4 (cid:0) (cid:0) (cid:0) 0 1 Start

r3

q7 q3 q4 q5 q6 q8

(cid:0) 1 Start q5 q6

r1 = r3r4 = 01*

r5

1 q1 q2 (cid:0) (cid:0)

(cid:0)

r = r1 + r2 = 01* + 1 Start

29 q8

q10 (cid:0) (cid:0) q9 (cid:0) (cid:0) (cid:0) 1 0 q3 q4 q7 q5 q6

(cid:0)

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) ij = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y (cid:0) x) thì l ≤ k} • Đặt Rk (hay Rk ij 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)

Rk

Rk-1

• Định nghĩa đệ quy của Rk ij = Rk-1

ij : kk)*Rk-1

ik(Rk-1

kj (cid:0)

ij

R0

ij =

{(cid:0) }, nếu i = j

{a | δ(qi, a) = qj}, nếu i ≠ j {a | δ(qi, a) = qj} (cid:0)

30

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 Rk

ij đều tồn tại một

biểu thức chính quy ký hiệu cho Rk

ij .

 k = 0: R0

ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc (cid:0)  Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại BTCQ rk-1

lm sao

cho L(rk-1

lm) = Rk-1

lm

 Vậy đối với Rk

rk

ik)(rk-1

kk)*(rk-1

kj) + rk-1

ij

ij ta có thể chọn BTCQ ij = (rk-1 → bổ đề đã được chứng minh ● Ta có nhận xét:

L(M) = (cid:0)

1j

qj (cid:0) F Rn ● Vậy L có thể được ký hiệu bằng BTCQ

r = rn

1j1 + rn

1j2 + … + rn

1jp

với F = {qj1, qj2, …, qjp}

31

Sự tương đương giữa DFA và BTCQ

Ví dụ: viết BTCQ cho DFA

1

1 Start 0 q2 q1 q3

Ta cần viết biểu thức:

0 0, 1

r = r3

12 + r3

13

Ta có: r3 •

12

r3

•

12 = r2 13 = r2

13(r2 13(r2

33)*r2 33)*r2

32 + r2 33 + r2

13

32

Sự tương đương giữa DFA và BTCQ

k = 0

k = 1

k = 2

(cid:0) (cid:0)

rk

(00)*

11

0

0

rk

0(00)*

12

1

1

rk

0*1

13

0

rk

0(00)*

21

(cid:0)

rk

(00)*

22

1

0 (cid:0) + 00 1 + 01

rk

0*1

23

(cid:0) (cid:0)

rk

(0 + 1)(00)*0

31

0 + 1

0 + 1

rk

32

(cid:0) (cid:0)

rk

(0 + 1)(00)* (cid:0) + (0 + 1)0*1

33

Thay vào và rút gọn, ta có:

r = 0*1((0 + 1)0*1)* ((cid:0) + (0 + 1)(00)*) + 0(00)*

33

Mối liên hệ giữa FA và BTCQ

Sơ đồ liên hệ:

ị

Đ nh lý

1

NFA

DFA

ị

ị

Đ nh lý

Đ nh lý

4

2

NFA(cid:0)

RE

ị

Đ nh lý

3

34