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

1 0 1 0 0 1 1 0

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)

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.

5

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

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ữ

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

q4

q0

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  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.

= δ( δ(q,w), 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) } • δ(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} )

δ

Input

Trạng thái q0 q1 q2 q3 q4

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

1 {q0,q1} {q2} {q2} Ø {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

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

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) = , δ(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]

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 1 2

Start 0, 1 1, 2 q0 q1 q2

0

1

2

Start

0, 1, 2

q0

q1

q2

Đị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  (Σ  {})

13

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)

14

0

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

2

Start

Ví dụ:

q0

q1

q2

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

• δ*(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}     )

15

= -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)

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, a) = δ*(q, a)

17

Sự tương đương giữa NFA và NFA

0 1 2

Start   q0 q2 q1

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 δ’

0 1 2

0 {q0, q1, q2} 

1 {q1, q2} {q1, q2} 

Trạng thái q0 q1 q2

2 {q2} {q2} {q2}

Start 0, 1 1, 2 q0 q2 q1

18

0, 1, 2

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

3 2     a b b Start 0 6 7 8 9 1 10

  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’ ↔ -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

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

Giải thuật:

20

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;

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

21

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

Xây dựng DFA từ NFA()

• Bảng hàm chuyển

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

B C A a b b

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

22

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

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, ... }

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)

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

25

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

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

r +  =  + r = r r + r = r r + s = s + r (r + s) + t = r + (s + t) = r + s + t

Phép hợp: • • • •

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

Tổng hợp: • • •

Phép bao đóng: * =  • • * =  r*r* = r* • (r*)* = r* • r* =  + r + r2 + … + rk + … • r* =  + r+ • ( + r)+ = ( + r)* = r* • r*r = r r* = r+ •

26

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 Start Start a q0 qf qf q0 q0

r = a r =  r = 

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

27

Các NFA cho các kết hợp đơn

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

• r = r1 + r2

M1   f1 q1 Start

q0 f0

  M2 q2 f2

• r = r1r2

Start  M1 M2 q1 f1 q2 f2

• r = r1*

Start   M1 q0 f1 f0

28

q1

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

  1 1 Start Start q7 q5 q8 q6 q1 q2

r4 = r5* = 1*

r2 0

Start q3 q4 0  1   Start q3 q4 q7 q6 q8 q5

r3 1

Start q5 q6

r1 = r3r4 = 01*

r5

1 q1 q2  

r = r1 + r2 = 01* + 1 Start

29

q10 q9      1 0 q3 q4 q7 q5 q6 q8

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

ij = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y  x) thì l ≤ k} ij là tập hợp tất cả các chuỗi làm cho automata đi từ

Chứng minh: • L được chấp nhận bởi DFA M({q1, q2,..., qn}, Σ, δ, q1, F) • Đặt Rk (hay Rk 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 Rk

ij :

Rk

ij = Rk-1 ik(Rk-1 kk)*Rk-1 kj  Rk-1

R0

30

ij = ij {a | δ(qi, a) = qj}, nếu i ≠ j {a | δ(qi, a) = qj}  {}, nếu i = j

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

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

• Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi Rk biểu thức chính quy ký hiệu cho Rk

ij .

ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc 

 k = 0: R0  Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại BTCQ rk-1

lm sao

lm) = Rk-1

lm

cho L(rk-1  Vậy đối với Rk

ij ta có thể chọn BTCQ

rk

ik)(rk-1

kk)*(rk-1

kj) + rk-1

ij

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

1j

L(M) = qj 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

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

1 Start 0 q3 q2 q1 0 0, 1

r = r3

12

Ta có: r3 • r3 •

12 = r2 13 = r2

13(r2 13(r2

33)*r2 33)*r2

32 + r2 33 + r2

13

32

12 + r3 13

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

k = 0

k = 1

k = 2

rk

(00)*

11

rk

0

0

0(00)*

12

1

1

0*1

13

rk rk

0

0

0(00)*

21

(00)*

 + 00

22

1

1 + 01

0*1

23

rk rk rk

(0 + 1)(00)*0

31

rk

0 + 1

0 + 1

(0 + 1)(00)*

32

rk

 + (0 + 1)0*1

33

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

r = 0*1((0 + 1)0*1)* ( + (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ý 4

Định lý 2

NFA

RE

Định lý 3

34