I

t

c

p u n

10100110

1

Start

1

i

B

0

0

a

b

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

q q 1 0 (cid:22) (cid:18) k h n u (cid:16) ñ i

• Khái niệm DFA & NFA

0

0

1

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

1

q q 2 3

• Sự tương ñương giữa DFA & NFA

x

d

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

• Biểu thức chính quy

• Các tính chất của tập chính quy

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

: 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 0 ∈ Q : trạng thái bắt ñầu.

F ⊆ Q : tập các trạng thái kết thúc.

3

1

εεεε

∀∀∀∀

Deterministic

Automata

∈∈∈∈

( Finite

Automata)

Ngôn ngữ chính quy

chuỗi nhập w=110101

Nondeterministic Automata Finite

4

2

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

Printed with FinePrint - purchase at www.fineprint.com

Finite 0

•

có thuộc ngôn ngữ

Q

kiểm tra một chuỗi nhập ñược chấp nhận bởi automata

.

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

chuỗi nhập

: 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 Σ → 0 ∈ Q : trạng thái bắt ñầu.

câu trả lời ‘

’ hoặc ‘

’

• • •

: khái niệm

F ⊆ Q : tập các trạng thái kết thúc. 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 := q0 ; c := nextchar ; { While c <> $ do

begin

εεεε

q := δ(q, c); c := nextchar ;

• •

có một trạng thái r trong

mà p∈

end

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

với ∀∀∀∀ ⊆⊆⊆⊆

•

∪∪∪∪ q∈P

5

7

•

cho automata M (hình vẽ) và xét chuỗi nhập

(cid:18) (cid:8) (cid:11) à ý i i t } h l k h h t ñ ñ e ư (cid:16) u p c n (cid:15) c c o p

•

1 0

1 0

Start

0

0

Input

1

0 1 2 3 4 0 2 4 q q q 3 4 0 δ

q0

q0

q0

q0

q0

q0

1

q3

q1

q3

q3

q1

0 1 0 0 1 q 1 0 1 0 0 1

q4

q4

0 1

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}

• Ứng với một trạng thái và một ký tự nhập, có thể có

∈∈∈∈

q 0 2 1

Do

không, một hoặc nhiều phép chuyển trạng thái.

6

8

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

Printed with FinePrint - purchase at www.fineprint.com

4 ∈∈∈∈ nên

εεεε

εεεε

NFA chấp nhận chuỗi 0+1+2+

Nếu

là tập ñược chấp nhận bởi một

thì tồn

0

1

2

tại một

chấp nhận

.

Start

0

1

2

chấp nhận L

q q q q 2 0 1 3 0

Giả sử Ta xây dựng

chấp nhận L

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

Q Một phần tử trong

•

ñược ký hiệu là [q0, q1,

0

1

2

…, qi] với q0, q1, …, qi ∈∈∈∈

Start

0

ε

ε

• •

là tập hợp các trạng thái của

có chứa ít nhất một

q q q 0 2 1 0 0

trạng thái kết thúc trong tập F của M

εεεε

:

i

j nếu và

• Hàm chuyển

i

0 1 2 1 2

j

chỉ nếu

• δ : hàm chuyển ánh xạ Q x ( ∪∪∪∪ εεεε ) → 2Q • Khái niệm

là tập hợp các trạng thái p sao cho

9

11

từ q tới p, với a ∈ (Σ ∪ {ε})

có phép chuyển nhãn

1 2 1 2

εεεε

NFA

với hàm chuyển

εεεε

(q0,0) = {q0, q1}, (q0,1) = {q1}, (q1,0) = ∅∅∅∅, (q1,1) = {q0, q1}

● εεεε ● εεεε

(q)

(q) = { p | có ñường ñi từ q tới p theo nhãn εεεε } (P) = ∪∪∪∪ q∈∈∈∈ P εεεε

0 1 0 1

Ta sẽ xây dựng DFA tương ñương

mở rộng

thành

Q x

→ 2Q

= {∅∅∅∅ [q0], [q1], [q0, q1]} = {[q1], [q0, q1]}

• •

(q, w) = { p | có ñường ñi từ q tới p theo nhãn

, trên

• • • Hàm chuyển

ñường ñi có thể chứa cạnh nhãn εεεε }

∅∅∅∅

∅∅∅∅

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

10

12

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

∅∅∅∅ ([q0], 0) = [q0, q1] ([q0], 1) = [q1] ([q1], 0) = ∅∅∅∅ ([q1], 1) = [q0, q1] ([q0, q1], 0) = [q0, q1] ([q0, q1], 1) = [q0, q1]

• δ*(R, w) = ∪∪∪∪ q∈∈∈∈ R δ*(q, w)

Printed with FinePrint - purchase at www.fineprint.com

0

εεεε

εεεε

0

1

2

Start

ε

ε

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.

εεεε M(Q, Σ, δ, q0, F) chấp nhận L

Xét chuỗi nhập • δ*(q0, εεεε) = ε-CLOSURE(q0) = {q0, q1, q2} • δ*(q0, ) = ε-CLOSURE(δ(δ*(q0, εεεε), 0))

M’={Q, Σ,

}

, q0,

Ta xây dựng: Với: •

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

= ε-CLOSURE(δ({q0, q1, q2}, 0)) = ε-CLOSURE(δ(q0, 0) ∪∪∪∪ δ(q1, 0) ∪∪∪∪ δ(q2, 0) ) = ε-CLOSURE( {q0} ∪∪∪∪ ∅ ∪ ∅ ) = ε-CLOSURE({q0}) = {q0, q1, q2}

• δ*(q0,

•

Ngược lại, (q, a) =

(q, a)

) = ε-CLOSURE(δ(δ*(q0, 0), 1)) = ε-CLOSURE(δ({q0, q1, q2}, 1)) = ε-CLOSURE({q1}) = {q1,q2}

• δ*(q0,

) = ε-CLOSURE(δ(δ*(q0, 01), 2)) = ε-CLOSURE(δ({q1, q2}, 2)) = ε-CLOSURE({q2}) = {q2}

13

15

• Do q2 ∈ F nên w ∈ L(M)

q q q 1 2 0

εεεε

εεεε

1

0

2

Start

ε

ε

mô phỏng hoạt ñộng của NFAε

chuỗi nhập

câu trả lời ‘YES’ (x ñược chấp nhận) hoặc ‘NO’

Xây dựng NFA tương ñương M’={Q, Σ,

}

, q0,

q q q 1 2 0

q := ε (cid:0) c := nextchar ; { While c <> $ do

δ’

Inputs

begin

R U S O L C E (q0) ; (cid:18) (cid:8) à ý i (cid:11) i l k h h t ñ ñ t } h u ư (cid:16) p e c n (cid:15) c c o p

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

0

1

2

q := ε (cid:0) c := nextchar ;

Start

L C O S U R E (δ(q, c));

0, 1

1, 2

0 {q0, q1, q2} ∅

end

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

∅

1 {q1, q2} {q1, q2} ∅

Trạng thái q0 q1 q2

2 {q2} {q2} {q2}

0, 1, 2

14

16

Printed with FinePrint - purchase at www.fineprint.com

q q q 0 2 1

εεεε

εεεε

xây dựng DFA tương ñương với NFAεεεε sau:

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

= (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10})

7, 8} →

ε

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

a

→

ε

ε

ε

ε

a

b

b

2 3

Start

ε

ε

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

0 1 6 7 8 9 1 0

b

7, 9} →

ε

Ta xây dựng

= (Q’, Σ, δ’, q0’, F’) tương ñương

● ε-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,

| trong ký hiệu của

có chứa ít nhất một trạng

• Trạng thái bắt ñầu: q0’ ↔ ε-CLOSURE(q0) • F’ = {

} →

6, 7,

thái của F }

17

19

• Xây dựng hàm chuyển δ’

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

4 5

εεεε

• Bảng hàm chuyển

T := ε (cid:10)

i

K

i

t

r

b

C

a

b

A

B

C

a

b

b

While C Begin

B

B

D

Start

E

A

B

D

a

b

For V

C

B

C

b

begin

a

a

D

B

E

a

If U

E

B

C

begin

• 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

δ [ end;

end;

thái 10 ∈ )

End;

18

20

Printed with FinePrint - purchase at www.fineprint.com

(cid:28) h ñ á ñ h d C O S L U R ư n ư c a (cid:24) c u ; E (q0) ; T ý N Q h h u p n á à $ h h á i Q ’ , ê t T T t t D F A o p m r v c c ’n g c a ; á T h U n g (cid:28) , ñ h d h ñ á ó 2 h á i t t T D F A t ư n r ’n g c a c a (cid:24) c ư m u do (cid:28) á h d ð T n u ; { xét trạng thái T} 6 5 i i k ý h i 9 h $ p m u n a do ) ) l T U : a c o s u r e , ( δ ( = ε (cid:10) $ k h ó h á i Q ’ , ô t t t t D F p n r r o n g ’n g g c c a A then á à $ h h á i Q ’ , ê t t t T U D F A o p r m v c c ’n g c a ; (cid:28) h ñ ñ h d á h á i t U T ư n r ư ’n g c a (cid:24) c ; u ] U T a : = , ; {δ[T, a] là phần tử của bảng chuyển DFA}

: là biểu thức chính quy biểu diễn tập {00}

• •

• • • •

• • • •

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

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

•

*

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

•

: tập hợp tất cả các chuỗi 0,1 có ít nhất

• • •

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

hai số 0 liên tiếp = {00, 000, 100, 0000, 0001, 1000, 1001, 011001, ... }

•

εεεε

: 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, 01, 02, 12, 012, 0012, 0112, ... }

• ε* = ε • ∅* = ∅ • r*r* = r* • (r*)* = r* • r* = ε + r + r2 + … + rk + … • r* = ε + r+ • (ε + r)+ = (ε + r)* = r* • r*r = r r* = r+

• •

: tất cả các chuỗi trong tập 0*1*2* với ít nhất

21

23

một ký hiệu 0, 1 và 2 ↔ viết gọn thành

+ + +

εεεε

cho Σ là một bộ chữ cái. BTCQ trên Σ là các tập

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)

quy nạp theo

• Xét không có phép toán nào

Start

Start

Start

a

q0

qf

qf

q0

q0

là các BTCQ ký hiệu cho các tập hợp R và là các BTCQ ký hiệu cho các ,

r = ε

r = ∅

r = a

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 ∈ Σ, là BTCQ ký hiệu cho tập {a} ● Nếu và S thì và tập hợp R ∪∪∪∪ S, RS và R* tương ứng

Các NFAε cho các kết hợp ñơn

• Xét có i phép toán: (cid:2) Xây dựng NFAεεεε

1 1 1 2, 2 hoặc

Σ2, δ2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2)

có thể viết là

• Biểu thức

như sau:

(cid:2) Xây dựng NFAεεεε

22

24

Printed with FinePrint - purchase at www.fineprint.com

1 = (Q1, Σ1, δ1, q1, {f1}) và 2 = (Q2,

εεεε

M1

ε

ε

f1

Nếu L ñược chấp nhận bởi một DFA, thì L ñược

q1

r

r

Start

• r

ký hiệu bởi một BTCQ

q0

f0

ε

ε

M2

q2

f2

+ = 2 1

M({q1, q2,..., qn}, Σ, δ, q1, F)

R

i

R

L ñược chấp nhận bởi DFA k

i

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

ε

Start

r

r

k

M1

M2

q1

f1

q2

f2

• r

• • ðặt (hay 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)

= 1 2

i

ε

• ðịnh nghĩa ñệ quy của Rk j = Rk-1

ij : kk)*Rk-1

ik(Rk-1

kj ∪ Rk-1

ij

*

r

k

Start

ε

ε

• r

M1

q0

q1

f1

f0

i

j

ε

{a | δ(qi, a) = qj}, nếu i ≠ j {a | δ(qi, a) = qj} ∪ {ε}, nếu i = j

25

27

= 1 0

εεεε

:

ε

• Quy nạp theo k (cid:2) k = 0: R0 ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc ε (cid:2) Giả sử ta có ñịnh lý ñúng với k-1, tức là tồn tại

xây dựng NFAε chấp nhận 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

ε

ε

1

1

• • • Start

Start

lm sao cho L(rk-1

lm) = Rk-1

lm

q7

q5

q8

q6

q1

q2

r

*

*

r

r

BTCQ rk-1 (cid:2) Vậy ñối với rk

ε

ε

0

Start

ik)(rk-1

q3

q4

r

2 1 = = 4 5

ε

ε

ε

0

1

Start

ij ta có thể chọn BTCQ kj) + rk-1 kk)*(rk-1 (rk-1 ij (cid:2) Ta có nhận xét:

q3

q4

q7

q6

q8

q5

*

3

r

r

r

ε

1

Start

1j

L(M) = ∪qj ∈F Rn

q5

q6

r

(cid:2) Vậy L có thể ñược ký hiệu bằng BTCQ

1

q1

q2

*

0 1 = = 1 3 4 5

ε

r

r

r

r = rn

1j1 + rn

1j2 + … + rn

1jp

ε

ε

Start

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

q10

q9

ε

ε

ε

ε

ε

1

0

q3

q4

q7

q5

q6

q8

26

28

ε

Printed with FinePrint - purchase at www.fineprint.com

0 1 1 + + = = 1 2

viết BTCQ cho DFA

l

h

ð

(cid:4)

n

1

ý 1

NFA

DFA

1

Start

0

q2

q1

q3

l

l

h

h

ð

ð

(cid:4)

(cid:4)

n

n

0

0, 1

ý 4

ý 2

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

l

h

ð

(cid:4)

NFAε

n

RE

ý 3

12

Ta có: r3 • r3 •

12 = r2 13 = r2

13(r2 13(r2

33)*r2 33)*r2

32 + r2 33 + r2

13

31

29

3 3 1 2 1 3

r

ε

ε

(00)*

r

0

0

0(00)*

r

1

1

0*1

r

0(00)*

r

0 ε

0 ε + 00

(00)*

r

0*1

r

1 ∅

1 + 01 ∅

(0 + 1)(00)*0

r

r

0 + 1 ε

0 + 1 ε

(0 + 1)(00)* ε + (0 + 1)0*1

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

εεεε

r =

30

Printed with FinePrint - purchase at www.fineprint.com

k 0 k 1 k 2 = = = k 1 1 k 1 2 k 1 3 k 2 1 k 2 2 k 2 3 k 3 1 k 3 2 k 3 3