NGÔN NGỮ HÌNH THỨC & ÔTÔMÁT

Ẵ

Ạ Ọ

KHOA CÔNG NGH THÔNG TIN

Đ I H C ĐÀ N NG Ạ Ọ NG Đ I H C BÁCH KHOA TR ƯỜ Ệ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

NGÔN NG HÌNH TH C & ÔTÔMÁT Ữ Ứ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

Gi

i thi u

ớ

ệ

M c tiêu giáo trình

ụ

ữ ấ

1. Cung c p nh ng ki n th c c b n ứ ơ ả v ngôn ng , văn ph m và ôtômát. ề ế ạ ữ

ng pháp phân

tích t 2. Cung c p các ph ấ ươ v ng, phân tích cú pháp. ừ ự

3. C s cho vi c tìm hi u các ngôn ể ệ

ng l p trình. ơ ở ữ ậ

Giáo trình Ki n trúc máy tính và H đi u hành

4. Rèn luy n k năng l p trình cho ậ ỹ

ệ ề

ệ sinh viên ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

Gi

i thi u

ớ

ệ

N i dung giáo trình

ộ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

CH

NG 3. BI U TH C VÀ VĂN PH M CHÍNH QUI

ƯƠ

Ứ

Ạ

Ể

CH

NG 4. VĂN PH M VÀ NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

CH

NG 6. MÁY TURING

ƯƠ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

 M t s v n đ v ngôn ng

ộ ố ấ ề ề

ữ

 Khái ni m văn ph m ệ

ạ

 Khái ni m Ôtômát ệ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- B ch (b ng ch ) là t p h p h u h n các ký ợ ữ ạ ộ ữ ả ữ ậ

hi uệ

Ví d :{0,1} b ch g m 2 ký hi u 0 và 1 ộ ữ ồ ụ ệ

{a,b,c,…,z} b ch g m các ký hi u a ộ ữ ồ ệ z

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

T p các ch cái ti ng vi ữ ế ậ t ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- Xâu trên b ch V là 1 dãy các ký hi u c a V ộ ữ ệ ủ

0110 là xâu trên b ch {0,1} Ví d :ụ ộ ữ

a, ab, giathanh là xâu trên b ch {a,b, ộ ữ

…,z}

- Đ dài xâu là s các ký hi u trong xâu ệ ộ ố

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế |01110|=5

Ký hi u:ệ đ dài xâu x là |x| ộ

Ví d :ụ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- Xâu r ng là xâu có đ dài b ng 0 ằ ộ ỗ

e , |e |=0 Ký hi u: ệ

*, {e }˝ V*

- T p t t c các xâu trên V là V ậ ấ ả

V+ =V *-{e }

V*: t p vô h n đ m đ c ậ ượ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ế V={a,b}V*={e ,a,b,aa,bb,ab,ba,…} Ví d :ụ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- Các phép toán trên xâu

ế

t x tr ế ủ ồ ế ướ

• Ghép ti p: cho 2 xâu x,y. Ghép ti p c a x, y là x.y hay xy là 1 xâu vi c, r i đ n y sau ế ch không có d u cách. ứ ấ

x=01 Ví d :ụ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế xy=010110

y=0110

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

r): xâu đ

c xâu x (x c vi ượ ế t theo th ứ

i c a xâu x • Đ o ng ượ ả t c l ng ự ượ ạ ủ

Ví d : ụ

e Chú ý: x=0101 xr =1010 r= e , 1r =1

- Xâu x mà x=xr thì x là xâu hình tháp (xâu đ i ố

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế Ví d : x=0110

x ng)ứ

xr=0110, x: xâu hình tháp ụ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

c b ng cách ậ ượ ằ

n): xâu nh n đ ầ

ghép ti p chính xâu x n l n. • Lũy th a xâu x (x ừ ế

xn = x.x.x...x (n l n x) ầ

x0 = e v i m i xâu x ớ ọ

x=01 x3 =010101 Ví d : ụ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

10= e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.2. Ngôn ngữ

- Ngôn ng L trên b ch V là t p h p các xâu ộ ữ ữ ậ ợ

trên V, L˝ V*

- Các phép toán trên ngôn ngữ

• Vì ngôn ng là t p h p nên có các phép toán ợ (h p), -(hi u), bù ữ ậ (giao), ¨ ợ ˙ t p h p: ậ ệ ợ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

• Ghép ti p 2 ngôn ng ế ữ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.2. Ngôn ngữ

- Các phép toán trên ngôn ng :ữ

Cho L1, L2 trên b ch V ộ ữ

• Phép giao: L1˙ L2 = {x | x˛ L1 và x˛ L2}

• Phép h p: L1 ợ ¨ L2 = {x | x˛ L1 ho c xặ ˛ L2}

• Phép hi u: L1- L2 = {x | x ˛ L1 và xˇ L2} ệ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

• Phép bù: L=V*- L

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.2. Ngôn ngữ

• Ghép ti p 2 ngôn ng ế ữ

ữ

ọ ộ ậ

Cho 2 ngôn ng L1, L2. Ta g i ghép ti p ế L1.L2 (L1L2) c a L1 và L2 là m t t p h p ợ ủ L1L2={xy/(x˛ L1) và (y˛ L2)}

Giáo trình Ki n trúc máy tính và H đi u hành

ế

ệ ề

x.x=x2; x.x.x=x3; x0=e ; xi=xi-1x L0={e }; Li=Li-1.L

- L*=L0¨ L1¨ L2¨ …¨ ; L+=L1¨ L2¨ …¨

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.3. Bi u di n ngôn ng ễ ể ữ

 Ngôn ng đ n gi n ả ữ ơ

- Ph ng pháp li ệ ố

c. ươ h u h n và có th xác đ nh đ ữ ạ t kê: ngôn ng có s xâu là ữ ượ ể ị

nhiên nh h n 20 ữ ố ự ỏ ơ

Ví d : ngôn ng là các s t và l n h n 12 ụ ớ ơ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

L={13, 14, 15, 16, 17, 18, 19}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.3. Bi u di n ngôn ng ễ ể ữ

 Ngôn ng đ n gi n ả ữ ơ

- Ph ươ ừ P(x): ngôn ng ữ

ng pháp s d ng tân t ử ụ mà các xâu có cùng các đ c đi m. ặ ể

Ví d : ngôn ng là các s th c nh h n 5. ố ự ỏ ơ ụ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ữ L={x/ (x˛ R) và (x<5)}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.3. Bi u di n ngôn ng ễ ể ữ

 Ngôn ng ph c t p ữ ứ ạ

- Văn ph m: c ch đ s n sinh ra ngôn ng ơ ế ể ả ạ ữ

ữ ự nhiên: văn ph m là h ệ ạ

- Đ i v i ngôn ng t th ng ng pháp. ố ớ ố ữ

ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ữ ậ t ch ng trình. - Đ i v i ngôn ng l p trình: văn ph m là qui ươ ố ớ t c cú pháp vi ắ ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.1. Đ nh nghĩa: G=(Σ, Δ, s, p) trong đó: ị

Σ: t p h u h n các ký hi u k t thúc. ậ ữ ạ ế ệ

Δ: t pậ hữu h nạ các ký hi uệ chưa k tế thúc. s: ký hi uệ b tắ đ uầ ; s˛ Δ

ữ ạ ác s nả xu tấ có d ngạ a b

p: t pậ h u h n c v iớ

- a ˛

Δ)+, có ít nh t m t ký hi u ch a ộ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ư ệ ấ

(Σ ¨ k t thúc ế

- b ˛ (Σ¨ Δ)*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.1. Đ nh nghĩa: G=(Σ, Δ, s, p) trong đó: ị

Σ: t p h u h n các ký hi u k t thúc. ậ ữ ạ ế ệ

Δ: t pậ hữu h nạ các ký hi uệ chưa k tế thúc. s: ký hi uệ b tắ đ uầ ; s˛ Δ

ữ ạ ác s nả xu tấ có d ngạ a b

p: t pậ h u h n c v iớ

- a ˛

Δ)+, có ít nh t m t ký hi u ch a ộ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ư ệ ấ

(Σ ¨ k t thúc ế

- b ˛ (Σ¨ Δ)*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

 Qui cướ :

- Ký hi uệ k tế thúc đ cượ vi tế b ngằ chữ th ngườ

- Ký hi uệ chưa k tế thúc đ cượ vi tế b ngằ chữ in

- Ký hi uệ chưa k tế thúc n mằ bên trái c aủ s nả

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

xu tấ đ uầ tiên là ký hi uệ b tắ đ uầ .

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph mạ

2.2. Các khái ni mệ

 Xâu (câu) và d ng câu: ạ

- a a g i là xâu khi ˛ Σ* ọ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- a a ˛ g i là d ng câu khi (Σ¨ Δ)* ạ ọ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.2. Các khái ni mệ

 Quan h suy d n: ệ ẫ

a ệ ẫ ượ

- A có quan h suy d n ra ừ c suy đ A áp d ng các s n ả hay a ụ

d n t ẫ ừ xu t sinh ra đ ấ A, có nghĩa là t ượ a c

- Quan h suy d n tr c ti p: t ừ A áp d ng m t ụ ộ

ự ế ẫ ệ ượ a c s n xu t sinh đ ấ ả

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

(cid:222) a ˛ ˛ Δ và a (Σ¨ Δ)* Ký hi u: Aệ v i Aớ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.2. Các khái ni mệ

 Quan h suy d n: ệ ẫ

A áp d ng ẫ ụ

+ a

- Quan h suy d n nhi u l n: t ề ầ nhi u s n xu t m i sinh đ ấ ệ ề ả ừ ượ a c ớ

(cid:222) ˛ ˛ Δ và a (Σ¨ Δ)* Ký hi u: A ệ v i Aớ

- Đ dài suy d n: s l n áp d ng các s n xu t ấ ố ầ ụ ẫ ả ộ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- Đ dài c a suy d n tr c ti p b ng 1 ẫ ự ế ủ ằ ộ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.3. Ngôn ng đ c sinh ra t văn ph m ữ ượ ừ ạ

c sinh ra t ượ ừ văn ph m s ẽ ạ

- T p h p các câu đ ợ ậ t o nên ngôn ng . ữ ạ

c sinh ra t văn ph m: - Xác đ nh câu đ ị ượ ừ ạ

ệ ừ ắ ầ ủ ụ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

T ký hi u b t đ u c a văn ph m áp d ng các s n xu t đ sinh các câu. ấ ể ả

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.3. Ngôn ng đ văn ph m ữ ượ ừ ạ

c sinh ra t (1) (2)

0S1 | e

- Ví d : cho G: S ụ (1) (2) S==>0S1==>01

(1) (1) (2)

S==>0S1==>00S11==>0011

(1) (1) (1) (2)

S==>0S1==>00S11==>000S111==>000111

n1n | v i n>=0}

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

V y L(G)={0 ậ ớ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.3. Ngôn ng đ c sinh ra t văn ph m ữ ượ ừ ạ

- Ví d 2: Cho G: SaA ụ

AaA | b

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

L(G)={anb | n>0}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.4. Phân c p văn ph m c a Chomsky ủ ạ ấ

- N u các s n xu t đ u có d ng A ạ a |aB v i ớ ấ ề

D S : văn ph m chính quy (VP lo i 3) ế A,B ˛ ả ;a ˛ ạ

˛ D - N u các s n xu t có d ng A ế v i Aớ ấ ạ ạ a

a ˛ ¨ D ả )*: văn ph m phi ng c nh (VP lo i 2) (S ; ạ ữ ả ạ

- N u các s n xu t có d ng , v i ớ a ạ ấ

b ˛ ¨ D a b ả )*: văn ph m c m ng c nh (VP lo i ế (S ữ ả ả ạ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- N u không có h n ch gì trên s n xu t: văn ấ ả

ạ ế do (VP lo i 0) ế ph m t ạ ự ạ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

2. Văn ph m ạ

2.4. Phân c p văn ph m c a Chomsky ủ ấ ạ

 L u ý:ư

ng h p đ c bi t c a ườ ặ ợ ệ ủ

- Văn ph m lo i 3 là tr ạ văn ph m lo i 2. ạ ạ ạ

ng h p đ c bi t c a ườ ặ ợ ệ ủ

- Văn ph m lo i 2 là tr ạ văn ph m lo i 1. ạ ạ ạ

ng h p đ c bi t c a ườ ợ ặ ệ ủ

ệ ề

- Văn ph m lo i 1 là tr ạ văn ph m lo i 0. ạ Giáo trình Ki n trúc máy tính và H đi u hành ạ ạ ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

3. Khái ni m Ôtômát ệ

ạ

- B g m: t p các tr ng thái và các đi u khi n ể tr ng thái này sang tr ng thái ề ạ

ậ ộ ồ d ch chuy n t ị ể ừ ạ khác khi nh n d li u vào. ậ ữ ệ

ủ ể

- Ôtômát bi u di n ho t đ ng c a bóng đi n ệ ễ ạ ộ n công t c ắ

ấ

B tậ

Tắ t - Ôtômát đoán nh n t

khóa int ậ ừ

i

n

t

int

Giáo trình Ki n trúc máy tính và H đi u hành

i ế

in ệ ề

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

 Ôtômát h u h n đ n đ nh(DFA)

ữ ạ ơ ị

 Ôtômát h u h n không đ n đ nh(NFA)

ữ ạ

ơ ị

 S t

ng đ

ng c a DFA và NFA

ự ươ

ươ

ủ

 ng d ng

Ứ

ụ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh(Deterministic ữ ạ ơ ị

finite automata –DFA)

1.1. Mô tả

- Ôtômát h u h n là m t cái máy đoán nh n ữ ạ ậ ộ

xâu g m:ồ

• M t băng vào đ c chia thành nhi u ô, m i ô ề ỗ

ch a m t ký hi u c a xâu vào ộ ượ ệ ủ ộ ứ

• M t đ u đ c, m i th i đi m tr vào m t ô ể ỗ ờ ọ ộ ỏ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ộ ầ trên băng

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.1. Mô tả

ể ạ

i ạ c xác ộ ộ ề ể ờ ỗ ượ

• M t b đi u khi n Q g m các tr ng thái, t m i th i đi m nó có m t tr ng thái đ đ nh qua hàm chuy n tr ng thái ể ị ồ ộ ạ ạ

Băng vào

Đ u đ c ầ ọ

q

B đi u ộ ề khi nể

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.1. Mô tả

ờ ộ ạ ở ộ ề

- T i m t th i đi m, tr ng thái q ể ệ ể

ạ khi n và ký hi u mà đ u đ c đang đ c s xác ầ đ nh tr ng thái ti p theo ị b đi u ọ ẽ ọ b đi u khi n. ể ở ộ ề ế ạ

- M i l n đ c xong m t ô, đ u đ c chuy n ỗ ầ ể ầ ọ ộ ọ

sang ph i m t ô. ả ộ

- Tr ng thái đ u tiên b đi u khi n: tr ng ạ ở ộ ề ể ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ầ thái b t đ u c a ôtômát

ệ ề

ắ ầ ủ ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

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

1.2. Đ nh nghĩa: ị

Σ: b ch vào ộ ữ

Q: t p h u h n các tr ng thái

ậ ữ ạ

ạ

Q: tr ng thái đ u

q0 ˛

ầ

ạ

F ˝

Q: t p các tr ng thái k t thúc

ế

ạ

ậ

ạ δ(q,a)=p

δ: hàm chuy n tr ng thái có d ng ạ V i q,p

Q, a ˛

Σ

ể ớ

V i m i

ỉ

ớ ỗ δ(q,a)=p ch có m t tr ng thái p duy nh t ấ 33

Giáo trình Ki n trúc máy tính và H đi u hành

ộ ạ ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.2. Đ nh nghĩa: ị

Σ, Q, δ, q0, F) - Ví d : DFA M( ụ

Σ: {0,1}

Q: {0,1}

q0: 0

Giáo trình Ki n trúc máy tính và H đi u hành

F: {1} t p các tr ng thái k t thúc ạ ế ậ

ế

δ: δ(0,0)=0, δ(0,1)=1, δ(1,1)=1 và δ(1,0)=0 ệ ề

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Otomat h u h n đ n đ nh ữ ạ ơ ị

1.3. Bi u di n các hàm chuy n tr ng thái ể ể ễ ạ

 Dùng b ng: s d ng ma tr n ử ụ ậ δ có: ả

- Ch s hàng: tr ng thái ỉ ố ạ

- Ch s c t: ký hi u vào ỉ ố ộ ệ

- Giá tr t i hàng q, c t a là tr ng thái p, ạ ộ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ị ạ sao cho δ(q,a)=p

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Otomat h u h n đ n đ nh ữ ạ ơ ị

1.3. Bi u di n các hàm chuy n tr ng thái ể ể ễ ạ

 Dùng b ng: ả

ộ

Ví d : có hàm chuy n c a m t Otomat nh ư ể ủ δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 ụ sau:

a

δ

b

c

2

1

2

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Otomat h u h n đ n đ nh ữ ạ ơ ị

1.3. Bi u di n các hàm chuy n tr ng thái ể ễ ể ạ

ể

 Bi u đ d ch chuy n: ồ ị ể ˛ Q đ - M i tr ng thái q c đ t trong các vòng ỗ ạ ượ ặ

tròn.

- Tr ng thái b t đ u q0 có thêm d u ‘>’ đ u. ắ ầ ạ ấ ở ầ

- Tr ng thái k t thúc q ˛ F đ c đ t trong vòng ế ạ ượ ặ

tròn kép.

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

- Các cung n i t tr ng thái q sang tr ng thái p có ạ ố ừ ạ ế

mang các nhãn a˛ Σ, có nghĩa δ(q,a)=p

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômat h u h n đ n đ nh ữ ạ ơ ị

1.3. Bi u di n các hàm chuy n tr ng thái ể ể ễ ạ

 Bi u đ d ch chuy n: ồ ị ể ể

ộ

Ví d : có hàm chuy n c a m t Otomat nh ư ể ủ δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 ụ sau:

b

a

c

2

1

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.4. Hàm chuy n tr ng thái m r ng ở ộ ể ạ

1a2a3...ai-1=yai-1

tr ng thái q - ọ

1đ c xong xâu x=a ạ

Ở ạ chuy n sang tr ng thái q ể

có th bi u di n nh sau: - Có d (q1,a1)=q2; d (q2,a2)=q3;..., d (qi-1,ai-1)=qi : ta ư ể ể ễ d *(q1,x)=qi

- ể ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

d *(q1,x)= d (d *(q1,y),ai-1)=qi: hàm chuy n tr ng thái m r ng. ở ộ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.4. Hàm chuy n tr ng thái m r ng ở ộ ể ạ

Cho δ: δ(0,0)=0, δ(0,1)=1, δ(1,1)=1 và δ(1,0)=0 Xác đ nh d *(0,01101)=?

ị d (0,0) = 0

d *(0,01) = d (d (0,0),1) = 1

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

d *(0,011) = d (d *(0,01),1) = 1

d *(0,0110) = d (d *(0,011),0) = 0 d *(0,01101) = d (d *(0,0110),1) = 1

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.5. Ho t đ ng đoán nh n xâu ạ ộ ậ

ệ

i ắ ầ ả ị

- T tr ng thái b t đ u, đ c t ng ký hi u vào ừ ạ t trái sang ph i. M i l n đ c thì xác đ nh l ỗ ầ ừ ạ tr ng thái qua hàm chuy n tr ng thái. ể ạ ọ ừ ọ ạ

ọ ạ ơ

- N u đ c xong xâu vào mà r i vào tr ng thái c ượ ượ

ế k t thúc thì xâu vào đ ế i xâu vào không đ l ạ c đoán nh n ng ậ c đoán nh n ậ ượ

ế

ệ ề

Giáo trình Ki n trúc máy tính và H đi u hành ượ

ể ọ ế c đoán nh n. không đ - N u không th đ c xong xâu vào thì xâu vào ậ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.5. Ho t đ ng đoán nh n xâu ạ ộ ậ

- Xâu x đ ượ ậ

(cid:219)

c đoán nh n b i ôtômat DFA ở d *(q0,x)=p˛ F - Cho DFA M({a,b},{0,1,2,3,4},d ,0,{4}),

δ: δ(0,a)=1, δ(1,b)=2, δ(2,a)=3, δ(2,b)=4

δ(3,a)=3, δ(3,b)=4, δ(4,b)=4

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

xâu x=abaabbb có đ c đoán nh n k0? ượ ậ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.5. Ho t đ ng đoán nh n xâu ạ ộ ậ

a

b

0

1

2

d (0,a) = 1

a

*(0,ab) = d (d (0,a),b) = 2

b

a

*(0,ab),a) = 3

3 (0,aba) = d (d (0,abaa) = d (d

*(0,aba),a) = 3

b

*(0,abaab) = d (d

*(0,abaa),b) = 4

4 *(0,abaabb) = d (d

*(0,abaab),b) = 4

*(0,abaabb),b) = 4˛ F, xâu x

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

đ

*(0,abaabbb) = d (d ế c đoán nh n ậ ượ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.5. Ho t đ ng đoán nh n xâu ạ ộ ậ

a

b

0

1

2

t l ể ế ạ i nh sau: ư

a

Ta có th vi 0abaabbb (cid:222) 1baabbb

b

a

(cid:222) 2aabbb

3

(cid:222) 3abbb

b

(cid:222) 3bbb

4

(cid:222) 4bb

(cid:222) 4b

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

(cid:222) 4˛ F, xâu x đ

c đoán nh n

ượ

ậ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

1.6. Ngôn ng đ c đoán nh n b i DFA ữ ượ ậ ở

c ượ

- Cho DFA M(Σ, Q, δ, q0, F), ngôn ng L đ c xác đ nh nh sau: ữ ư ượ ở

S đoán nh n b i M đ ậ L(M)={x˛ ị *| d *(q0,x)=p˛ F}

- Ví d : v ôtômat đoán nh n ngôn ng L g m ụ ẽ ữ ồ

ố ị ậ ộ

các xâu là s nh phân có đ dài >=2 0|1

0 2 1 Giáo trình Ki n trúc máy tính và H đi u hành

0|1 ệ ề

0|1 ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

 Tr ng thái không ch p nh n đ c ậ ượ ạ ấ

- Tr ng thái không có mũi tên đi vào ch có mũ ạ ỉ

tên đi ra (tr tr ng thái b t đ u). ắ ầ ừ ạ

- Tr ng thái ch có mũi tên đi vào không có mũi ạ

tên đi ra (tr tr ng thái k t thúc ế ỉ ừ ạ

q

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

 Bài t p:ậ

(1) Cho M, xâu x: ki m tra xâu x có đ c đoán ượ

ể nh n hay không? ậ

x: aabbca, abbbca, abbaca, aaaca

a

b

a

b

c

a

2

0

1

3

4

Giáo trình Ki n trúc máy tính và H đi u hành

c

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

 Bài t p:ậ

(2) Xây d ng DFA đoán nh n ngôn ng L(M) ữ ự ậ

- L(M)={abcnbm v i n>=0, m>0} ớ

- L(M)={0(10)n v i n>0} ớ

- L(M)={0n1m v i n>=0, m>0} ớ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- L(M)={0n1m v i n>0, m>0} ớ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

1. Ôtômát h u h n đ n đ nh ữ ạ ơ ị

 Bài t p:ậ

(3) Xây d ng ôtômat đoán nh n L(M) là: ự ậ

- M t s nh phân ch n có đ dài xâu l n h n ẵ ộ ố ộ ơ ớ ị

- M t s nguyên có d u, không d u. ộ ố ấ ấ

- M t s nguyên không d u c a NNLT C ấ ủ ộ ố

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- M t s th c tĩnh có d u, không d u. ộ ố ự ấ ấ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

(Nondeterministic finite automata –NFA)

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

2.1. Đ nh nghĩa: ị

Σ: b ch vào ộ ữ

Q: t p h u h n các tr ng thái

ậ ữ ạ

ạ

Q: tr ng thái đ u

q0 ˛

ầ

ạ

F ˝

Q: t p các tr ng thái k t thúc

ế

ạ

ậ

δ: hàm chuy n tr ng thái có d ng ạ

ể

(Σ¨

ạ δ(q,a)=P ), P˝ Q

V i qớ ˛ Q, a˛

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

Ví d : Ôtômát đoán nh n các xâu có đ dài ộ ụ

ậ ch n trên b ch {0,1} ộ ữ ẵ

0|1

0

1

2

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

ự ữ

e (Σ¨ ), P˝ Q  S khác nhau gi a DFA và NFA - NFA: δ(q,a)=P, v i qớ ˛ Q, a˛

˛ DFA: δ(q,a)=p, v i q,p Q, a ˛ Σ ớ

ể ể

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

ọ e - NFA: có th có d ch chuy n khi đ c ị ọ e DFA: không th d ch chuy n khi đ c ể ị ể

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

2.2. Hàm d ch chuy n m r ng

- ị ể d (q0,a1)={q1, q2} và

ở ộ d (q1,a2)={q3,q4} d (q2,a2)={q5,q6}

(

), i ap

- d d *(q0,a1a2)= d (q1,a2)¨ (q2,a2)={q3,q4,q5,q6}

= 1

*, a˛

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

S S d *(q,xa)= - Có d *(q,x)={p1, p2,...,pk} thì  v i xớ ˛

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

2.2. Hàm d ch chuy n m r ng ở ộ ể ị

- Cho NFA, d *(0,01001)=?

0

1

0

1

2 0|1

d (0,0)={1} d *(0,01)= d (1,1)={1,2}

d *(0,010)= d (1,0) ¨ d (2,0) ={1}

d *(0,0100)= d (1,0) ={1}

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

d *(0,01001)= d (1,1) ={1,2}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

2.3. Đoán nh n xâu x b i NFA ở ậ

- Xâu x đ ượ ở

(cid:219) F c đoán nh n b i ôtômat ậ d *(q0,x)˙ F„

- Theo ví d tr c: ụ ướ

d *(0,01001)= {1,2}

F : xâu 01001 đ c đoán ượ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

{1,2}˙ F ={2} „ nh nậ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

2. Ôtômat h u h n không đ n đ nh ữ ạ ơ ị

2.4. Ngôn ng đ c đoán nh n b i NFA ữ ượ ậ ở

c ượ

- Cho NFA M(Σ, Q, δ, q0, F), ngôn ng L đ c xác đ nh nh sau: ữ ư ị ở

S F đoán nh n b i M đ ậ L(M)={x˛ F„ } ượ *| d *(q0,x) ˙

- Theo ví d tr ằ

ụ ướ ằ c các xâu b t đ u b ng 0 và ắ ầ c đoán nh n: 00111, ậ ượ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

k t thúc b ng 1 đ ế 0100101, 0111, 010101,...

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

NFA 3. Xây d ng DFA t ự ừ

- Cho NFA M(ΣN, QN, δN, q0, FN) thì DFA M(ΣN, QD, δD, q0, FD)

- Xác đ nh Qị

D, δD, FD

ạ ấ ả

ậ

ừ ậ

• T o t t c các t p con T t

t p Q N

˛ T, a˛

d d S

ị

• Xác đ nh

D(T,a)=¨

N(qi,a) v i qớ i

ng ng v i 1 tr ng thái c a

• M i t p T t ỗ ậ

ươ ứ

ủ

ớ

ạ

DFA

ệ ề

• Lo i b các tr ng thái không ch p nh n đ c ậ ượ 57 Giáo trình Ki n trúc máy tính và H đi u hành

ạ ỏ

ạ ế

ấ

• Tr ng thái t

ng ng v i t p T có ch a tr ng

ạ

ươ ứ

ớ ậ

ứ

ạ

thái k t thúc s là tr ng thái k t thúc c a DFA

ủ

ế

ẽ

ạ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

NFA 3. Xây d ng DFA t ự

- Ví d :ụ

ừ 0|1

0

1

0

1

2

{0}

{0} {0,1}

q0

{2}

{1}

*{2}

*q2

{0,1} {0,1}

{0,2}

*{0,2} {0,1}

{0}

* q4

*{1,2}

{2}

ệ ề

ế

* q5 Giáo trình Ki n trúc máy tính và H đi u hành * q6

{0,2}

*{1,2,0} {0,1}

q2 58 q4

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

NFA 3. Xây d ng DFA t ự ừ

1

0

- Ví d :ụ

0

1 q4

q0

q3

q0

0

1

*q2

q1

0

1

*q4

q2

q6

q5

*q5

*q6

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

- Các tr ng thái q1, q2, q5, q6: không ch p nh n

NFA 3. Xây d ng DFA t ự ừ

ậ

ạ

ấ

đ

cượ

- q4 t

ươ ứ

ng ng {0,2}: là tr ng thái k t thúc ạ

ế

1

0

1

q0

q0

q3

q4

0

*q4

1

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

4. Ứ ng d ng ụ

- Đoán nh n t khóa, s , ..., t ậ ừ ố t ừ ố

- DFA đoán nh n khóa float ậ

f

l

o

a

t

0

1

2

3

4

5

- NFA đoán nh n s nguyên có d u ấ ậ ố

0|..|9

+| - |e

0|..|9

2

Giáo trình Ki n trúc máy tính và H đi u hành

0 ế

1 ệ ề

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

 Bài t pậ

(1) V NFA đoán nh n ẽ ậ

- các s nh phân có đ dài là b i s c a 4. ộ ộ ố ủ ố ị

- các t 110, 101. ừ

- Các t 0(101) ừ

(2) Chuy n NFA thành DFA ể

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- Các NFA câu (1) ở

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

 Bài t pậ

- NFA ở

0|1

hình v sau: ẽ 0|1

0 0|1

0

2

1

3

0

- NFA có hàm chuy n sau: ể

a

b

c

d

0

{1,2}

{1}

{2}

{0}

{2}

{0,1}

1

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

*2

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

 Bài t pậ

- NFA có hàm chuy n sau: ể

0

1 {1}

0

{1,3}

{2}

{1,2}

*1

{3}

{0}

2 {0}

*3

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

 Bi u th c chính quy ứ

ể

 Ngôn ng chính quy ữ

 Văn ph m chính qui ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

ị

ứ

1.1. Đ nh nghĩa: ộ ữ S Cho b ch đ , bi u th c chính quy ể c đ nh nghĩa đ qui nh ư ượ ị ệ

(BTCQ) trên S sau:

- F là BTCQ

- e là BTCQ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- S " a˛ , a là BTCQ

- V i r, s là BTCQ thì (r+s), rs, r*, s* là BTCQ ớ

¨ Có th vi t (r+s) hay (r s) ể ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.1. Đ nh nghĩa: ị

S ={0,1} ta có: Ví d : Cho ụ

- F , e , 0, 1 là BTCQ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

(0+1), 01, 0*, 1*, (0+1)01, (0+1)0*, (01)*, ((0+1)01)* là BTCQ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.1. Đ nh nghĩa: ị

 Ví d :ụ

- ỉ

(a+b+c) là BTCQ ch đ nh 3 xâu a, b, c trên b ộ ị ch {a, b, c} ữ

- (a+b)* là BTCQ ch đ nh m i xâu trên {a, b} ị ọ ỉ

- ỉ

ằ ộ ố ị ế

ệ ề

ế

ệ ấ ệ Giáo trình Ki n trúc máy tính và H đi u hành

aa*bb* hay a+b+ là BTCQ ch đ nh các xâu b t ắ đ u b ng m t s ký hi u a, ti p theo là m t ộ ệ ầ s ký hi u b trong đó ký hi u a và b xu t hi n ệ ố ít nh t 1 l n ầ ấ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.1. Đ nh nghĩa: ị

 Ví d :ụ

- ị ỉ

(b+e )(a+ab)* là BTCQ ch đ nh các xâu trên {a, b} không ch a bbứ

- ố ị

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

(0+1)*1 là BTCQ ch đ nh các xâu là s nh ị ỉ phân lẻ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.2. Th t u tiên c a các phép toán ứ ự ư ủ

- Phép bao đóng (*)

- Phép ghép ti p (.) ế

- Phép h p (+) ợ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

(1(0)*)+0  Ví d : 10*+0 : ụ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.3. Tính ch t đ i s ấ ạ ố

- Tính giao hoán:

r + s = s + r

- Tính k t h p: ế ợ

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

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

r(st)=(rs)t

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.3. Tính ch t đ i s ấ ạ ố

- Tính ch t phân b ấ ổ

r (s + t) = rs + rt

(r + s)t = rt + st

- M t s tính ch t khác ộ ố

(r*)* = r* e *= e

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

r + r = r ấ e r = re = r r* = r+ + e

r+ = rr* = r*r (r*s*)* =(r + s)*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.4. Ngôn ng đ c ch đ nh b i BTCQ ữ ượ ở ỉ ị

c ch đ nh b i BTCQ r ở ị

Ngôn ng L(r) đ ữ ượ ỉ c xây d ng d a trên quy t c ắ ự ượ ự

b t kỳ là đ ấ - L(e ) = {e }

- L(a) = {a} - L(r+s)=L(r)¨ L(s)

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- L(rs) = L(r)L(s)

- L(r*) = (L(r))*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

1.4. Ngôn ng đ c ch đ nh b i BTCQ ữ ượ ở ỉ ị

ụ ữ ị ỉ

 Ví d : xây d ng BTCQ ch đ nh ngôn ng L ệ ự ộ ệ ấ

có ít nh t m t ký hi u a và 1 ký hi u b trên {a, b}

- L(r) = L(r1) ¨ L(r2)=L(r1+r2)

1aw2bw3

- L(r1): các xâu r1 có d ng wạ

1bw2aw3

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- L(r2): các xâu r2 có d ng wạ

- BTCQ ch đ nh L: ỉ ị

(a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

 Bài t pậ

(1) Xây d ng BTCQ ch đ nh các ngôn ng sau: ỉ ữ ự ị

- T p h p các xâu trên {a,b} có đ dài chia h t ế ợ ộ

ậ cho 3

- T p h p các xâu trên {a, b, c} ch ch a 1 ký ỉ ứ

ợ hi u a, còn l i là các ký hi u b và c ậ ệ ạ ệ

ệ ề

- T p h p các s nh phân có t n cùng là 11 ị ậ ậ ố ợ

Giáo trình Ki n trúc máy tính và H đi u hành ấ ợ

ế ố

- T p h p các s nguyên k0 d u chia h t cho 5 ế ậ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

1. Bi u Th c chính quy ứ ể

 Bài t pậ

(2) Mô t ngôn ng đ ả ữ ượ c ch đ nh b i BTCQ sau: ở ị ỉ

- (a+b+c+d)*(a+d)

- 1(0+1)(0+1)(0+1)

- ((0+1)(0+1))+

- a(a+b)*a

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- (ab)* + (ba)*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.1. Khái ni mệ

ữ ữ ượ c bi u ể

- Ngôn ng chính quy là ngôn ng đ di n b i bi u th c chính qui. ứ ễ ể ở

c đoán nh n b i ượ ậ ở

- Ngôn ng chính qui đ ữ ôtômát h u h n. ữ ạ

- Ngôn ng đ ừ văn ph m chính ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

c s n sinh t ữ ượ ả quy là ngôn ng chính qui ữ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.2. Ôtômat NFA đoán nh n ngôn ng đ c ữ ượ ậ

bi u di n b i BTCQ ễ ở ể

- BTCQ là a

a

- BTCQ là e

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.2. Ôtômat NFA đoán nh n ngôn ng đ c ữ ượ ậ

bi u di n b i BTCQ ễ ở ể

- BTCQ là rs

r

s

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.2. Ôtômat NFA đoán nh n ngôn ng đ c ữ ượ ậ

bi u di n b i BTCQ ễ ở ể

- BTCQ là (r+s)

r

e e

s

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.2. Ôtômat NFA đoán nh n ngôn ng đ c ữ ượ ậ

bi u di n b i BTCQ ễ ở ể

- BTCQ là r*

e e

r

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.2. Ôtômat NFA đoán nh n ngôn ng đ c ữ ượ ậ

bi u di n b i BTCQ ễ ở ể

- Ví d : xây d ng NFA đoán nh n (0+1)(01)* ụ ự ậ

0

e e

1

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.2. Ôtômat đoán nh n ngôn ng đ ữ ượ ậ c bi u ể

di n b i BTCQ ễ ở

- Ví d : (0+1)(01)* ụ

e e

0

1

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

0

e e

0

1

e e

1 0|1

0

1

0

2

3

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

2.3. Tính ch t đóng c a ngôn ng chính quy ủ ữ ấ

Cho L1(r) và L2(s) là ngôn ng chính quy thì: ữ

L2(s): ngôn ng chính quy ữ

- L1(r) ¨ - L1(r) ˙ L2(s): ngôn ng chính quy ữ

- L1(r).L2(s): ngôn ng chính quy ữ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- (L1(r))*: ngôn ng chính quy ữ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

 Bài t pậ

(1) V NFA đoán nh n ngôn ng đ c bi u di n ữ ượ ậ ễ ể

ẽ b i BTCQ sau: ở

- (01)*(0+10*)

- (10+(0+01)1*0)

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- (0+1)*(11+00)(0+1)*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

2. Ngôn ng chính quy ữ

 Bài t pậ

(2) V DFA đoán nh n ngôn ng đ c bi u di n ữ ượ ậ ể ễ

ẽ b i BTCQ sau: ở

- 1*01+

- 10*11*

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- (a+b)c*ab*

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

3.1. Đ nh nghĩa văn ph m tuy n tính trái ế ạ ị

- M t văn ph m G=(

ộ ạ Σ, Δ, s, p) đ ế ấ ả ế

ạ ph m tuy n tính trái n u t có d ng Aạ Bw hay AB v i A,B c g i là văn ượ ọ t c các s n xu t ả ấ ˛ Δ; w˛ Σ* ớ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- Ví d : Sụ S a | S b | a

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

3.2. Đ nh nghĩa văn ph m tuy n tính ph i ả ế ạ ị

- M t văn ph m G=( ạ ượ ọ

ộ ạ ế Σ, Δ, s, p) đ ả ế ấ ả

ph m tuy n tính ph i n u t có d ng Aạ wB hay AB v i A,B c g i là văn t c các s n xu t ấ ả ˛ Δ; w˛ Σ* ớ

Sa A - Ví d : ụ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

Aa A | b A | e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

3.3. Đ nh nghĩa văn ph m chính quy ạ ị

ế ế ạ

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

tính ph i là văn ph m chính quy. - Văn ph m tuy n tính trái, văn ph m tuy n ạ ạ ả

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

văn ph m tuy n tính 3.4. Xây d ng NFA t ự ừ ế ạ

ph iả

Cho văn ph m chính qui G=( ạ

G xây d ng NFA M=(Q, ự c sinh ra t ngôn ng đ ữ ượ ΣG , Δ, s, p) Σ, q0, d , F) đoán nh n ậ ừ

- Σ = ΣG

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

˛ Δ thì A˛ Q - V i Aớ

- q0 = S

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

văn ph m tuy n tính 3.4. Xây d ng NFA t ự ừ ế ạ

ph iả

- N u Aế a1a2...ai thì d *(A,a1a2...ai)=qi : thêm qi

vào Q và F

d các d ch chuy n ị - N u Aế a1a2...ai thì đ t vào

ạ ớ

a2

ai

...

A Giáo trình Ki n trúc máy tính và H đi u hành

qi 92

ể ặ tr ng thái và thêm vào Q các tr ng thái m i ạ sao cho d *(A,a1a2...ai)=qi a1 ế

ệ ề

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

văn ph m tuy n tính 3.4. Xây d ng NFA t ự ừ ế ạ

ph iả

ị - N u Aế a1a2...aiB thì đ t vào

d các d ch ạ ạ

ặ chuy n tr ng thái và thêm vào Q các tr ng thái ể m i sao cho ớ d *(A,a1a2...ai)=B

a1

a2

ai

...

A

B

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- N u Aế e thì thêm A vào F

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

văn ph m tuy n tính 3.4. Xây d ng NFA t ự ừ ế ạ

ph iả

Sa A - Ví d : ụ

Aa A | b A | e

a |b

a

S

A

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

3.4. Xây d ng văn ph m chính quy t NFA ự ạ ừ

ự

ph m chính qui G=( Cho NFA M=(Q, Σ, q0, d , F) xây d ng văn ΣG , Δ, s, p) ạ

- ΣG = Σ

- Δ=Q

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- S=q0

˛ - qap n u ế d (q,a)=p - qe n u q F ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

3.4. Xây d ng văn ph m chính quy t NFA ự ạ ừ

Ví d : ụ

a |b

a

- ΣG = {a,b}

S

A

- Δ={S, A}

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

- S=S - SaA vì d (S,a)=A ; AaA vì d (A,a)=A

- AbA vì d (A,b)=A; Ae vì A ˛ F

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

 Bài t pậ

(1) V otomat NFA t G sau: ẽ ừ

- S0S| 1S | 1

- S + A |- A

A0 A| 1A| ..| 9A |0|..|9

- SabA

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

AbB| B

Bc

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

3. Văn ph m chính quy ạ

 Bài t pậ

(2) Xây d ng G t NFA sau: ự ừ

0|1

0 0|1

0 C

B

D

A

Giáo trình Ki n trúc máy tính và H đi u hành

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng ươ ươ

S * có 4.1. Tr ng thái t ạ - V i ớ " w˛

{p, q} là c p ặ tr ng thái ạ mà t ng ươ ho c cùng ặ ng. đ ươ d *(p,w)=ql và d * (q,w)=qt qt, ql cùng k t thúc ế không k t thúc ế

- {q,p} và {p,k} các c p tr ng thái t ng ươ

Giáo trình Ki n trúc máy tính và H đi u hành

ế

ạ ng đ thì c p {q,k} cũng t ặ ươ ươ ng đ ươ ng (t/c b t c u) ắ ầ ặ

ng đ ệ ề ng đ c g i là ươ ượ ọ

- Hai tr ng thái không t ươ t. hai tr ng thái phân bi ệ ạ ạ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

- Xây d ng b ng đánh d u c p tr ng thái phân ấ ặ ự ả ạ

bi tệ

(1) N u p là tr ng thái không k t thúc và q là tr ng ế ế ạ

thái k t thúc thì {p,q} là tr ng thái phân bi ạ t. ệ

S ạ có d (p,a)=ql và d (q,a)=qt mà {qt, ql} là

t thì {p, q} c p tr ng thái ặ ệ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

100

ệ ề

ế

ế (2) V i aớ ˛ c p tr ng thái phân bi ạ ặ phân bi t.ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

ấ ặ ạ

 Ví d : xây d ng b ng đánh d u c p tr ng ả ự t cho otomat sau ụ thái phân bi ệ

0 0,1

B

E

0 0,1

1 0,1

A

G

D

1

0

1 F

C

101

ệ ề

ế

1 Giáo trình Ki n trúc máy tính và H đi u hành

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

- Ta có B, D, E, G: tr ng thái k t thúc ế ạ

A,C,F: tr ng thái không k t thúc ế ạ

Áp d ng (qt1) nên các c p sau là phân bi t: ụ ặ ệ

{A,B}, {A,D}, {A,E}, {A,G},

Giáo trình Ki n trúc máy tính và H đi u hành

102

{C,B}, {C,D}, {C,E}, {C,G},

ệ ề

{F,B}, {F,D}, {F,E}, {F,G} ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

- Đánh d u x vào các ô là c p tr ng thái phân ấ ặ ạ

bi tệ

B

X

C

X

D

X

E

X

F

X

G

X

Giáo trình Ki n trúc máy tính và H đi u hành

103

A

ế B

C

ệ ề D

E

F

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

- Áp d ng (qt2) đ i v i t ng c p tr ng thái ố ớ ừ ặ ạ

ụ phân bi t ệ

• {A,B}, {A,D}, {A,E}, {A,G}: vì A là tr ng ạ

thái b t đ u nên không có qt2. ắ ầ

• {C,B}: đ c t o ra t cùng tr ng thái A nên ượ ạ ừ ạ

k0 có (qt2)

104

ệ ề

ế

• {C,D}: d (A,1)=C và d (B,1)=D nên {A,B} phân

Giáo trình Ki n trúc máy tính và H đi u hành ấ ồ

t (đã đánh d u r i) bi ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

• {C,E}: k0 có a th a (qt2) ỏ

• {C,G}: d (A,1)=C và d (E,1)=G nên {A,E} phân

bi t (đã đánh d u r i) ệ ấ ồ

• {F,B}: k0 có a th a (qt2) ỏ

• {F,D}: d (C,1)=F và d (B,1)=D nên {C,B} phân

Giáo trình Ki n trúc máy tính và H đi u hành

105

ệ ề

ế

bi t (đã đánh d u r i) ệ ấ ồ

• {F,E}: k0 có a th a (qt2) ỏ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

• {F,G}:

t (đã ệ

d (E,1)=G và d (C,1)=F nên {C,E} phân bi đánh d u r i) ấ ồ

t (đã ệ

d (G,1)=G và d (C,1)=F nên {G,C} phân bi đánh d u r i) ấ ồ

t (đã ệ

ệ ề

ế

d (F,1)=F và d (G,1)=G nên {F,G} phân bi đánh d u r i) ấ ồ

c c p tr ng thái phân bi 106 t ượ ặ Giáo trình Ki n trúc máy tính và H đi u hành ạ ệ

Ta k0 tìm thêm đ nào

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

c b ng đánh d u tr ng thái phân bi t ượ ả ạ ấ ệ

- Ta đ sau

B

X

C

X

D

X

E

X

F

X

G

X

A

C

B

E

D Giáo trình Ki n trúc máy tính và H đi u hành

F 107

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

ng đ ng 4.1. Tr ng thái t ạ ươ ươ

- Ta đ c các c p tr ng thái t ng đ ng sau: ượ ặ ạ ươ ươ

Giáo trình Ki n trúc máy tính và H đi u hành

108

ệ ề

ế

{A,C}, {A,F}, {B,D}, {B,E}, {B,G}, {C,F}, {D,E}, {D,G}, {E,G}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

4.2. Hai otomat t ng đ ng ươ ươ

- Hai otomat cùng đoán nh n m t ngôn ng thì ữ ậ ộ

ng đ ng. t ươ ươ

ng đ ươ ng thì c p tr ng thái đ u ạ ặ ầ

ng đ ươ ng. - Hai DFA t ươ t ươ

- C c ti u hóa DFA: tìm DFA t ng đ ng có ươ ươ

Giáo trình Ki n trúc máy tính và H đi u hành

109

ệ ề

ế

ự ể s tr ng thái ít nh t. ố ạ ấ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

4.3. Thu t toán ậ

- Lo i b các tr ng thái không ch p nh n đ ạ ỏ c ậ ượ ạ ấ

t c các c p tr ng thái t ng ấ ả ạ ặ ươ

đ - Xác đ nh t ị ngươ

- Chia các tr ng thái thành các nhóm, sao cho: ạ

• ng ộ ươ

110

ệ ề

ế

ạ ng nhau các tr ng thái trong cùng m t nhóm t đ ươ

Giáo trình Ki n trúc máy tính và H đi u hành ở

2 nhóm khác

• Không có c p tr ng thái nào ặ ng đ nhau là t ng. ạ ươ ươ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

4.3. Thu t toán ậ

min(S,a)=T khi " q˛ S thì d (q,a)=p˛ T

- d

min là tr ng thái có ch a tr ng

ạ ầ ứ ạ ạ

- Tr ng thái đ u M thái đ u c a M ầ ủ

min là nh ng tr ng thái có

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

Giáo trình Ki n trúc máy tính và H đi u hành

111

ệ ề

ế

ữ ch a tr ng thái k t thúc c a M ạ ứ ủ ế ạ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

4.3. Thu t toán ậ

 Ví d : C c ti u hóa DFA ví d tr ụ ự ể ở c ụ ướ

ng đ - Ta có các c p tr ng thái t ặ ươ ươ ạ

ng sau: {A,C}, {A,F}, {B,D}, {B,E}, {B,G}, {C,F}, {D,E}, {D,G}, {E,G}

- T o thành các nhóm tr ng thái t ng đ ng: ạ ạ ươ ươ

{A,C,F}, {B,D,E,G}

1 0|1

0

Giáo trình Ki n trúc máy tính và H đi u hành

ế

ACF ệ ề

BDEG 112

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

 Bài t p: ậ C c ti u các DFA sau: ự ể

d (1)

0

1 B

A

F

G

B

C

A

*C

C

D

G

H

E

F

C

F

G

E

H

G Giáo trình Ki n trúc máy tính và H đi u hành

113

C ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 3. BI U TH C & VĂN PH M CHÍNH QUY

ƯƠ

Ứ

Ạ

Ể

4. C c ti u hóa DFA ự ể

 Bài t p: ậ C c ti u các DFA sau: ự ể

d (2)

0

1 B

A

E

D

B

C

*C

C

E

D

C

D

*E

C

Giáo trình Ki n trúc máy tính và H đi u hành

114

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

 Văn ph m phi ng c nh

ữ ả

ạ

 S nh p nh ng trong văn ph m phi ng c nh

ự ậ

ữ ả

ằ

ạ

 Ngôn ng phi ng c nh

ữ ả

ữ

 D ng chu n c a văn ph m phi ng c nh

ẩ ủ

ữ ả

ạ

Giáo trình Ki n trúc máy tính và H đi u hành

115

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

1. Văn ph m phi ng c nh ữ ả ạ

 Đ nh nghĩa: ị

G=(Σ, Δ, s, p) trong đó:

Σ: t p h u h n các ký hi u k t thúc. ậ ữ ạ ế ệ

Δ: t pậ hữu h nạ các ký hi uệ chưa k tế thúc. s: ký hi uệ b tắ đ uầ ; s˛ Δ

Giáo trình Ki n trúc máy tính và H đi u hành

116

ệ ề

ế

˛ p: t pậ h u h n c ữ ạ ác s nả xu tấ có d ngạ (Σ¨ Δ)* Aa v iớ A˛ Δ và a

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

1. Văn ph m phi ng c nh ữ ả ạ

 Ví d : ụ

Giáo trình Ki n trúc máy tính và H đi u hành

117

ệ ề

ế

SS(S)S | e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

1. Văn ph m phi ng c nh ữ ả ạ

 Suy d n trái, suy d n ph i ả ẫ ẫ

- N u luôn luôn thay th ký hi u ch a k t thúc ế ư ế ệ

ế bên trái nh t g i là suy d n trái. ấ ọ ẫ ở

- T ng t ươ ự ta có suy d n ph i ả ẫ

- Ví d : vi ụ ả ạ ế ẫ ẫ

xâu a+a*a c a văn ph m sau: t suy d n trái, suy d n ph i t o ra ủ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

118

ệ ề

ế

EE+E |E*E| (E) |a

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

1. Văn ph m phi ng c nh ữ ả ạ

 Cây suy d n: ẫ cây tho mãn các đi u ki n: ề ệ ả

- M i nút có 1 nhãn: ký hi u k t thúc ho c ệ ế ặ

ch a k t thúc ỗ ư ế

- Nhãn c a nút g c: ký hi u b t đ u ắ ầ ố ủ ệ

- Nhãn c a nút lá: ký hi u k t thúc ủ ệ ế

ộ ủ

119

ệ ề

ế

- N u m t nút có nhãn A có các nút con c a nó ế trái sang ph i có nhãn x1, x2, x3, …xn thì t ừ ả Ax1x2x3…xn ˛ p Giáo trình Ki n trúc máy tính và H đi u hành

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

1. Văn ph m phi ng c nh ữ ả ạ

 Cây suy d nẫ

- Suy d n trái t o ra cây suy d n trái. ạ ẫ ẫ

- Suy d n ph i t o ra cây suy d n ph i ả ả ạ ẫ ẫ

- Ví d : v cây suy d n trái, cây suy d n ph i ả ẫ ụ ẽ ẫ

t o ra xâu a+a*a c a văn ph m sau: ủ ạ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

120

ệ ề

ế

EE+E |E*E| (E) |a

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

2. S nh p nh ng trong văn ph m phi ng ữ ự ậ ằ ạ

c nhả

 Khái ni m văn ph m nh p nh ng ệ ậ ạ

- Cho văn ph m phi ng c nh G. N u ạ ữ ả

ừ ẫ

ằ ế $ x˛ L(G) 2 cây suy d n khác nhau thì G ằ đ ượ đ ượ ọ c sinh ra t c g i là văn ph m nh p nh ng ạ ậ

Giáo trình Ki n trúc máy tính và H đi u hành

121

ệ ề

ế

EE+E | E*E | (E) | a - Ví d :ụ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

2. S nh p nh ng trong văn ph m phi ng ữ ự ậ ằ ạ

c nhả

 Kh s nh p nh ng ử ự ậ ằ

- Đ a vào văn ph m lu t u tiên ậ ư ư ạ

Giáo trình Ki n trúc máy tính và H đi u hành

122

ệ ề

ế

- Đ t th a s chung ừ ố ặ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

2. S nh p nh ng trong văn ph m phi ng ữ ự ậ ằ ạ

c nhả

ằ

Giáo trình Ki n trúc máy tính và H đi u hành

123

ệ ề

ế

 Kh s nh p nh ng ử ự ậ - Ví d : Sụ aS | aSbS | e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

3. Ngôn ng phi ng c nh ữ ả ữ

c sinh ra t ậ ừ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

124

ệ ề

ế

ượ phi ng c nh là ngôn ng phi ng c nh - T p h p các xâu đ ợ ữ ả văn ph m ữ ả ữ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Khái ni m ệ

Văn ph m phi ng c nh k0 ch a: ữ ả ứ ạ

• Ký hi u th a ệ

ừ ấ e • S n xu t ả

• S n xu t đ n v ấ ơ ả ị

d ng ượ ọ ữ ả ạ ở ạ

Giáo trình Ki n trúc máy tính và H đi u hành

125

ệ ề

ế

Đ c g i là văn ph m phi ng c nh chu n ẩ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Xác đ nh và kh ký hi u th a ử ừ ệ ị

- Ký hi u th a có 2 lo i: ừ ệ ạ

• Ký hi u vô sinh ệ

• Ký hi u k0 đ t đ n đ c ạ ế ượ ệ

˛ D đ - Ký hi u Aệ ượ ọ c g i là ký hi u vô sinh khi ệ

a ˛ S A(cid:222)

Giáo trình Ki n trúc máy tính và H đi u hành

126

ệ ề

˛ D ượ ọ c g i là ký hi u k0 đ t đ n ệ ạ ế

(cid:222) đ đ +a Ab ế - Ký hi u Aệ c khi S ượ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Xác đ nh và kh ký hi u th a ừ ử ệ ị

- Ví d : xác đ nh ký hi u th a c a VP sau: ừ ủ ệ ị

ụ (1) S0S | 1S | A| e

A0A

(2) S0S | 1S | e

Giáo trình Ki n trúc máy tính và H đi u hành

127

ệ ề

ế

A0A | 1

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Xác đ nh và kh ký hi u th a ử ừ ệ ị

- Xác đ nh ký hi u k0 vô sinh:

" S k0 vô sinh

k0 vô ị ệ e k0 vô sinh " a˛ • V i Aớ a ộ a mà m i ký hi u thu c ệ ọ

sinh thì A k0 vô sinh.

Giáo trình Ki n trúc máy tính và H đi u hành

128

ệ ề

ế

- Ký hi u k0 ph i là ký hi u k0 vô sinh thì là ký ệ ả

ệ hi u vô sinh ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Xác đ nh và kh ký hi u th a ử ừ ệ ị

- Xác đ nh ký hi u đ t đ n đ c: ạ ế ượ ệ ị

c ạ ế ượ

c • S là ký hi u đ t đ n đ ệ • V i Aớ a

ệ mà A là ký hi u đ t đ n đ ạ ế ượ ệ là ký hi u đ t ạ ệ

c. ộ a thì m i ký hi u thu c ọ đ n đ ế ượ

ạ ế ệ ệ

Giáo trình Ki n trúc máy tính và H đi u hành

129

ệ ề

ế

- Ký hi u k0 ph i là ký hi u đ t đ n thì là ký c hi u k0 đ t đ n đ ả ạ ế ượ ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Xác đ nh và kh ký hi u th a ử ừ ệ ị

- Kh ký hi u th a: ừ ử ệ

ệ

• Lo i b t ấ ạ ỏ ấ ả s n xu t ch a nó. ả t c các ký hi u vô sinh và các ứ

ạ ế

Giáo trình Ki n trúc máy tính và H đi u hành

130

ệ ề

ế

c và các s n xu t ch a nó. đ • Lo i b t ượ ạ ỏ ấ ả ả t c các ký hi u k0 đ t đ n ệ ứ ấ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Xác đ nh và kh ký hi u th a ử ừ ệ ị

- Ví d : Kh ký hi u th a c a các văn ph m: ừ ủ ệ ạ ử

ụ (1) S0S | 1S | A| e

A0A

(2) S0S | 1S | e

Giáo trình Ki n trúc máy tính và H đi u hành

131

ệ ề

ế

A0A | 1

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ữ ả ạ ạ

ẩ ủ ấ e  Kh s n xu t ử ả

(cid:222) - A là bi n tri t tiêu khi A ế ệ

t tiêu: - Xác đ nh bi n tri ị ệ

ế • A e thì A: bi n tri t tiêu ế ệ

t ế ệ

Giáo trình Ki n trúc máy tính và H đi u hành

132

ệ ề

ế

• AC1C2...Cn n u Cế 1, C2,...,Cn là bi n tri t tiêu tiêu thì A là bi n tri ệ ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ữ ả ạ ạ

, S, p), kh s n xu t c ượ

ẩ ủ ấ e  Kh s n xu t ử ả - Cho G(S , D G’(S ớ ị

ớ

ấ e ta đ , D ử ả , S, p’) v i p’ xác đ nh nh sau: ư ỗ B1B2...Bn ˛ p ta thêm các V i m i A Ax1x2...xn vào p’ trong đó m i xỗ i thay th Bế i th a mãn: ỏ

i là bi n k0 tri ế

i=Bi

t tiêu đ c thì x • N u Bế ệ ượ

133

ệ ề

ế

i là bi n tri ế

i=e và xi=Bi

t tiêu thì x • N u Bế ệ Giáo trình Ki n trúc máy tính và H đi u hành

i=e

t c các x • Không cho t ấ ả

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ữ ả ạ ạ

ẩ ủ ấ e  Kh s n xu t ử ả

- Ví d : kh s n xu t ử ả ụ ấ e c a văn ph m : ủ ạ

SAB AaAB | e

Giáo trình Ki n trúc máy tính và H đi u hành

134

ệ ề

ế

BbAB | e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ữ ả ạ ạ

ẩ ủ ấ e  Kh s n xu t ử ả

- Ta có S, A, B: là bi n tri t tiêu ế ệ

- Xét SAB có

A là bi n tri t tiêu nên thay A b ng e và A ế ệ ằ

B là bi n tri t tiêu nên thay B b ng e và B ế ệ ằ

Giáo trình Ki n trúc máy tính và H đi u hành

135

ệ ề

ế

ta đ c: S ượ AB | B | A

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ữ ả ạ ạ

ẩ ủ ấ e  Kh s n xu t ử ả

- Xét AaAB ta đ c: A ượ aAB | aB | aA | a

- Xét BbAB ta đ c: B ượ bAB| bB | bA | b

V y ta đ ậ ượ c văn ph m sau: ạ

SAB | B | A

AaAB | aB | aA | a

Giáo trình Ki n trúc máy tính và H đi u hành

136

ệ ề

ế

BbAB| bB | bA | b

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ữ ả ạ ạ

ẩ ủ ấ e  Kh s n xu t ử ả

 Bài t p: kh s n xu t ử ả ậ ấ e c a các văn ph m ủ ạ

(1) S0S |1S | e

(2) SS(S)S | e

Giáo trình Ki n trúc máy tính và H đi u hành

137

ệ ề

ế

(3) Sa S b | b S a | e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 S n xu t đ n v ấ ơ ị ả

ạ B đ ượ ọ c g i là s n xu t ả ấ

˛ D - S n xu t có d ng A ấ ả đ n v ; v i A,B ị ớ ơ

Giáo trình Ki n trúc máy tính và H đi u hành

138

ệ ề

ế

- C p (A,B) c p bi n c a s n xu t đ n v ế ủ ả ấ ơ ặ ặ ị

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

ử ả ị

S  Kh s n xu t đ n v ấ ơ ị , D , D ử ả Cho G(S c G’( đ , S, p), kh s n xu t đ n v ta , S, p’) v i p’ xác đ nh nh sau: ượ ấ ơ ị ư ớ

- Thêm các s n xu t không đ n v vào p’ ấ ả ơ ị

+B (ch s ỉ ử

(cid:222) - Xác đ nh các c p bi n (A,B) mà A ặ ị

d ng các s n xu t đ n v ) ị ụ ả ế ấ ơ

ớ ỗ ặ

139

- V i m i c p bi n (A,B) xác đ nh ở ị ế ; v i Bớ a trên, thêm là s n ả

vào p’ các s n xu t A ả ế ệ ề xu t không đ n v trong G ơ ấ a Giáo trình Ki n trúc máy tính và H đi u hành ị ấ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Kh s n xu t đ n v ấ ơ ị ử ả

- Ví d : Kh s n xu t đ n v cho văn ph m ấ ơ ử ả ụ ạ ị

SaA |A | bB

AB | a

Giáo trình Ki n trúc máy tính và H đi u hành

140

ệ ề

ế

BA | ab | bb

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Kh s n xu t đ n v ấ ơ ị ử ả

- Ta có các s n xu t không đ n v : ị ả ấ ơ

SaA| bB

Aa

Bab |bb

- Ta có các c p bi n (S,A), (S,B), (A,B), (B,A) ặ

+B; A(cid:222)

+B; B(cid:222)

Giáo trình Ki n trúc máy tính và H đi u hành

141

ệ ề

ế

(cid:222) th a mãn S ế +A; S(cid:222) ỏ

• a nên thêm: Sa c p (S,A), có A ặ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Kh s n xu t đ n v ấ ơ ị ử ả

• ab và Bbb nên thêm:

c p (S,B), có B ặ Sab |bb

• ab và Bbb nên thêm:

c p (A,B), có B ặ Aab |bb

Giáo trình Ki n trúc máy tính và H đi u hành

142

ệ ề

ế

• a nên thêm: Ba c p (B,A), có A ặ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Kh s n xu t đ n v ấ ơ ị ử ả

V y ta đ ậ ượ c văn ph m sau: ạ

SaA | a | ab |bb |bB

Aa | ab | bb

Giáo trình Ki n trúc máy tính và H đi u hành

143

ệ ề

ế

Bab |bb | a

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 4. VĂN PH M & NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

4. D ng chu n c a văn ph m phi ng c nh ẩ ủ ữ ả ạ ạ

 Kh s n xu t đ n v ấ ơ ị ử ả

 Bài t p: kh s n xu t đ n v cho văn ph m ấ ơ ử ả ậ ạ ị

(1) S0A | 1 A | A

AS | 0 | 1

(2) EE+T | T

Giáo trình Ki n trúc máy tính và H đi u hành

144

ệ ề

ế

TT*F | F

F(E) | a

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

 Ôtômat đ y xu ng (PDA) ẩ

ố

 Ngôn ng đ

c đoán nh n PDA

ữ ượ

ậ

 S t

ng đ

ng gi a PDA và văn ph m phi

ươ

ữ

ạ

ự ươ ng c nh ữ ả

 Ôtômat đ y xu ng đ n đ nh

ơ ị

ố

ẩ

Giáo trình Ki n trúc máy tính và H đi u hành

145

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ẩ

ố (Push Down Automat - PDA)

1.1. Mô t ả

Băng vào

Đ u đ c ầ ọ

q B đi u khi n

ộ ề

ể

Giáo trình Ki n trúc máy tính và H đi u hành

146

ệ ề

ế Ngăn x pế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.1. Mô t ả

T i m t th i đi m b đi u khi n: ộ ể ể ể ạ ộ ờ

• Tr ng thái q ạ

e : k0 • Đ c m t ký hi u trên băng vào ( ệ ộ

ọ đ c) ọ

• Nhìn ký hi u đ nh ngăn x p ệ ở ỉ ế

ệ ề

ế

ị ế ị ạ

Giáo trình Ki n trúc máy tính và H đi u hành ộ

xác đ nh tr ng thái ti p theo và quy t đ nh ế 147 hành đ ng liên quan đ n ngăn x p ế ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.1. Mô t ả

ể ậ ố

Có 2 cách đ ôtômát đ y xu ng đoán nh n ẩ xâu vào:

• Đ c xong xâu vào và ôtômat tr ng thái k t ở ạ ế

ọ thúc

Giáo trình Ki n trúc máy tính và H đi u hành

148

ệ ề

ế

• Đ c xong xâu vào và ngăn x p r ng ế ỗ ọ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

M(Σ, Q, G

, z, δ, q0, F)

1.2. Đ nh nghĩa: ị

Σ: b ch vào ộ ữ

Q: t p h u h n các tr ng thái

ậ ữ ạ

ạ

q0 ˛

Q: tr ng thái đ u

ạ

ầ

Q: t p các tr ng thái k t thúc

ế

ạ

ậ

F ˝ G

: t p ký hi u trên ngăn x p

ế

ệ

ậ

z ˛

G

: ký hi u đ u tiên ệ ầ

ở ỉ

ế

Giáo trình Ki n trúc máy tính và H đi u hành

)} 149

ệ ề

δ: hàm chuy n tr ng thái d ng ế , a V i q,p

ể Q, a ˛

{e }, x˛

ạ Σ¨

đ nh ngăn x p ạ δ(q,a,x)={(p,a G

G *

˛

ớ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

M(Σ, Q, G

, z, δ, q0, F)

1.2. Đ nh nghĩa: ị

)}

δ: hàm chuy n tr ng thái d ng , a V i q,p

ể Q, a ˛

{e }, x˛

ạ Σ¨

ạ δ(q,a,x)={(p,a G

G *

˛

ớ

X: ký hi u

đ nh ngăn x p

ệ ở ỉ

ế

đ nh ngăn x p

: chu i ký hi u thay th x ệ

ế ở ỉ

ỗ

ế

a = e : ký hi u x trên đ nh ngăn x p đ

c l y ra

ế ượ ấ

ệ

ỉ

a =x: ngăn x p không thay đ i. ổ

ế

a =yz: l y x ra, đ y z vào, đ y y vào. ẩ

ấ

ẩ

Giáo trình Ki n trúc máy tính và H đi u hành

150

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

nbn

1.2. Đ nh nghĩa ị

ụ

ậ , z, δ, q0, F)

M(Σ, Q, G

Ví d : Otomát đ y xu ng đoán nh n các xâu a ố ẩ v i n>=0: ớ

Σ: {a,b}

Q: {q0, q1, q2, q3}

ạ

q0: tr ng thái đ u ầ

ế

ậ

{q3}: t p các tr ng thái k t thúc ạ

ế

{1,z} : t p ký hi u trên ngăn x p ệ ậ Giáo trình Ki n trúc máy tính và H đi u hành

151

ệ ề

ế

đ nh ngăn x p

z : ký hi u đ u tiên ệ ầ

ở ỉ

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.2. Đ nh nghĩa ị

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

Giáo trình Ki n trúc máy tính và H đi u hành

152

ế

ệ ề

δ(q0,e ,z)={(q3,e )}

δ(q1,a,1)={(q1,11)} δ(q1,b,1)={(q2,e )} δ(q2,b,1)={(q2,e )} δ(q2,e ,z)={(q3,e )}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.3. Bi u di n PDA b ng bi u đ d ch ể ồ ị ễ ằ

ể chuy n ể

c đ t trong các vòng tròn - Các tr ng thái đ ạ ượ ặ

- Tr ng thái đ u có d u “>” g n phía tr c ấ ầ ắ ạ ướ

- Tr ng thái k t thúc đ t trong vòng tròn kép ế ặ ạ

- ): t tr ng thái q sang tr ng thái ừ ạ ạ

Giáo trình Ki n trúc máy tính và H đi u hành

153

ế

δ(q,a,x)=(p,a p có nhãn a, x|a

ệ ề ế

c là z - Ký hi u đ u đ nh ngăn x p qui ỉ ệ ầ ướ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.3. Bi u di n PDA b ng bi u đ d ch ể ồ ị ễ ằ

ể chuy n ể

nbn v i ớ

- Ví d : v ôtômat PDA đoán nh n xâu a ụ ẽ ậ

n>=0

a,1|11

b,1|e

a,z|1z

b,1|e

,z|e

q3

q1

q2

q0

,z|e

Giáo trình Ki n trúc máy tính và H đi u hành

154

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.4. C u hình c a PDA ủ ấ

C u hình c a PDA là b (q,w, a ): ủ ấ ộ

- q: tr ng thái ạ

- w: ph n xâu vào s đ c ẽ ọ ầ

Giáo trình Ki n trúc máy tính và H đi u hành

155

ệ ề

ế

- a : n i dung c a ngăn x p (đ nh-đáy: trái-ph i) ế ủ ả ộ ỉ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

1. Ôtômat đ y xu ng ố ẩ

1.4. C u hình c a PDA ủ ấ

ví d tr c đoán ụ ấ ủ ở ụ ướ

Ví d : C u hình c a PDA nh n xâu: aaabbb ậ

- Có nghĩa (q0,aaabbb,z) |-* (q3,e ,e ) : xâu vào

Giáo trình Ki n trúc máy tính và H đi u hành

156

ệ ề

đ ượ c đoán nh n ậ ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.1. Đoán nh n b i tr ng thái k t thúc ậ ở ạ ế

c PDA M đoán nh n b i ữ ượ ậ ở

- Ngôn ng L đ ế

˛ F, tr ng thái k t thúc là: ạ L(M)={w | (q0,w,z ) |-* (qf ,e ,a )} v i qớ f

Giáo trình Ki n trúc máy tính và H đi u hành

157

ệ ề

ế

a ˛ G *

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.2. Đoán nh n b i ngăn x p r ng ậ ở ế ỗ

c PDA M đoán nh n b i ngăn ở ượ ậ

Giáo trình Ki n trúc máy tính và H đi u hành

158

ệ ề

ế

˛ Q - Ngôn ng L đ ữ x p r ng : ế ỗ L(M)={w | (q0,w,z ) |-* (qk ,e ,e )} v i qớ k

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

 Bài t p: ậ v PDA đoán nh n xâu x là: ẽ ậ

(1) anbmcm v i n,m>=0 ớ

(2) anbmcn v i n,m>0 ớ

ng thích (3) Các c p d u () t ặ ấ ươ

(4) S nh phân có s ch s 0 b ng s ch s 1 ố ữ ố ố ữ ố ằ ố ị

(5) bi u th c s h c d ng h u t có 1 s h ng ứ ố ọ ở ạ ậ ố ể ố ạ

ệ ề

ế

159 (6) S nh phân có s ch s 0 g p đôi s ch s ố ữ ố ố ữ ố

Giáo trình Ki n trúc máy tính và H đi u hành ấ

ị

ố 1 và xâu khác e

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.3. Chuy n PDA t ể ậ ở ừ

đoán nh n b i ngăn x p ậ ở ạ ế

ế r ng sang đoán nh n b i tr ng thái k t ỗ thúc

, z, δ, q0) đoán nh n ậ Σ, Q’, G ’, z’, δ’,

ế Cho PDA M(Σ, Q, G b i ngăn x p r ng thành M’( ế ỗ ở q0’, F) đoán nh n b i tr ng thái k t thúc có: ở ạ ậ

- Q’=Q¨ {q0’,qf}

Giáo trình Ki n trúc máy tính và H đi u hành

160

ệ ề

ế

- F={qf}

- G ’=G ¨ {z’}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.3. Chuy n PDA t ể ậ ở ừ

đoán nh n b i ngăn x p ậ ở ạ ế

ế r ng sang đoán nh n b i tr ng thái k t ỗ thúc e

,z’| e

- δ’ đ c xác đ nh: ượ ị

,z’|zz’

,z’| e ,z’| e

M

qf

q0

q0’

Giáo trình Ki n trúc máy tính và H đi u hành

161

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.3. Chuy n PDA t ể ậ ở ừ

đoán nh n b i ngăn x p ậ ở ạ ế

ế r ng sang đoán nh n b i tr ng thái k t ỗ thúc

Ví d : ụ

a,z|1z a,1| 11b,1|

,z|e

q0

q1

Giáo trình Ki n trúc máy tính và H đi u hành

162

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.3. Chuy n PDA t ể ậ ở ừ

đoán nh n b i ngăn x p ậ ở ạ ế

ế r ng sang đoán nh n b i tr ng thái k t ỗ thúc

Ví d : ụ

a,z|1z a,1| 11b,1|

,z|e

q0

q1

a,z| 1za,1| 11b,1|

e e e

,z|e

,z’|zz’

,z’|e

q0’

q0

q1

qf

Giáo trình Ki n trúc máy tính và H đi u hành

163

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.3. Chuy n PDA t ể ậ ở ừ

đoán nh n b i ngăn x p ậ ở ạ ế

ế r ng sang đoán nh n b i tr ng thái k t ỗ thúc

Ví d : ụ

a,z| 1za,1| 11b,1|

,z|e

q0

q1

Giáo trình Ki n trúc máy tính và H đi u hành

164

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.3. Chuy n PDA t ể ậ ở ừ

đoán nh n b i ngăn x p ậ ở ạ ế

n v i n>0

ế r ng sang đoán nh n b i tr ng thái k t ỗ thúc

Ví d : (ab) ụ ớ

a,z|zz

,z|e

a,z|zz b,z|e

q0

q1

q3

Giáo trình Ki n trúc máy tính và H đi u hành

165

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.4. Chuy n PDA t ể ừ

đoán nh n b i tr ng thái ậ ở ạ cu i sang đoán nh n b i ngăn x p r ng ậ ở ế ỗ

, z, δ, q0, F) đoán nh n ậ Σ,Q’,G ’, z’, ế ố Cho PDA M(Σ, Q, G b i ngăn x p r ng thành M’( ế ỗ ở δ’,q0’) đoán nh n b i tr ng thái k t thúc có: ở ạ ậ

- Q’=Q¨ {q0’,qk}

Giáo trình Ki n trúc máy tính và H đi u hành

166

ệ ề

ế

- G ’=G ¨ {z’}

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.4. Chuy n PDA t ể ừ

đoán nh n b i tr ng thái ậ ở ạ cu i sang đoán nh n b i ngăn x p r ng ậ ở ế ỗ ố

- δ’ đ c xác đ nh: ượ ị

e a ˛ G

,"

’| e

,z’|zz’

e a ˛ G

,"

’| e

M

qk

q0

q0’

e a ˛ G

’| e

,"

Giáo trình Ki n trúc máy tính và H đi u hành

167

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.4. Chuy n PDA t ể ừ

đoán nh n b i tr ng thái ậ ở ạ cu i sang đoán nh n b i ngăn x p r ng ậ ở ế ỗ ố

Ví d : aụ nbm v i n,m>=0 ớ

a,z|1z a,1|11

b,1|11

b,z|1z b,1|11

q0

q1

,z|z

Giáo trình Ki n trúc máy tính và H đi u hành

168

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

2. Ngôn ng đ c đoán nh n b i PDA ữ ượ ậ ở

2.4. Chuy n PDA t ể ừ

đoán nh n b i tr ng thái ậ ở ạ cu i sang đoán nh n b i ngăn x p r ng ậ ở ế ỗ ố

Ví d : aụ nbn v i n>=0 ớ

,z|e ,1|e

a,z|1z a,1|11

b,1|11

b,z|1z b,1|11

,z|e ,1|e

q0

q1

qf

,z|z

Giáo trình Ki n trúc máy tính và H đi u hành

169

ệ ề

ế

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

3. Ôtômat đ y xu ng đ n đ nh ơ ị ố ẩ

- Ôtômát đ y xu ng th a mãn: ố ẩ

(1 )" ỏ d (q,a,X) ch ch a m t giá tr duy nh t ấ ỉ ứ ị

Giáo trình Ki n trúc máy tính và H đi u hành

170

ệ ề

ế

ộ d (q,e ,X) ph i r ng (2 )d (q,a,X) không r ng thì ả ỗ ỗ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

4. S t ng đ ng gi a PDA và văn ph m phi ươ ữ ạ

ự ươ ng c nh ữ ả

4.1. Chuy n văn ph m phi ng c nh thành ữ ả ể ạ

PDA

- B ch (b ng ch ) là t p h p h u h n các ký ợ ữ ạ ộ ữ ả ữ ậ

hi uệ

Ví d :{0,1} b ch g m 2 ký hi u 0 và 1 ộ ữ ồ ụ ệ

{a,b,c,…,z} b ch g m các ký hi u a ộ ữ ồ ệ z

171

ế ậ t ệ Giáo trình Ki n trúc máy tính và H đi u hành T p các ch cái ti ng vi ữ ế ệ ề

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

4. S t ng đ ng gi a PDA và văn ph m phi ươ ữ ạ

ự ươ ng c nh ữ ả

4.2. Chuy n PDA thành văn ph m phi ng ữ ể ạ

c nhả

- B ch (b ng ch ) là t p h p h u h n các ký ợ ữ ạ ộ ữ ả ữ ậ

hi uệ

Ví d :{0,1} b ch g m 2 ký hi u 0 và 1 ộ ữ ồ ụ ệ

{a,b,c,…,z} b ch g m các ký hi u a ộ ữ ồ ệ z

172

ế ậ t ệ Giáo trình Ki n trúc máy tính và H đi u hành T p các ch cái ti ng vi ữ ế ệ ề

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 6. MÁY TURING

ƯƠ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- B ch (b ng ch ) là t p h p h u h n các ký ợ ữ ạ ộ ữ ả ữ ậ

hi uệ

Ví d :{0,1} b ch g m 2 ký hi u 0 và 1 ộ ữ ồ ụ ệ

{a,b,c,…,z} b ch g m các ký hi u a ộ ữ ồ ệ z

Giáo trình Ki n trúc máy tính và H đi u hành

173

ệ ề

ế

T p các ch cái ti ng vi ữ ế ậ t ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 6. MÁY TURING

ƯƠ

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- B ch (b ng ch ) là t p h p h u h n các ký ợ ữ ạ ộ ữ ả ữ ậ

hi uệ

Ví d :{0,1} b ch g m 2 ký hi u 0 và 1 ộ ữ ồ ụ ệ

{a,b,c,…,z} b ch g m các ký hi u a ộ ữ ồ ệ z

Giáo trình Ki n trúc máy tính và H đi u hành

174

ệ ề

ế

T p các ch cái ti ng vi ữ ế ậ t ệ

NGÔN NGỮ HÌNH THỨC & ÔTÔMÁT

Cung cấp những kiến thức cơ bản về ngôn ngữ, văn phạm và ôtômát. Cung cấp các phương pháp phân tích từ vựng, phân tích cú pháp. Cơ sở cho việc tìm hiểu các ngôn ngữ lập trình. Rèn luyện kỹ năng lập trình cho sinh viên

Ạ Ọ

KHOA CÔNG NGH THÔNG TIN

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

Gi

i thi u

ớ

ệ

M c tiêu giáo trình

ụ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

Gi

i thi u

ớ

ệ

N i dung giáo trình

ộ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

CH

NG 2. ÔTÔMÁT H U H N

ƯƠ

Ữ

Ạ

CH

NG 3. BI U TH C VÀ VĂN PH M CHÍNH QUI

ƯƠ

Ứ

Ạ

Ể

CH

NG 4. VĂN PH M VÀ NGÔN NG PHI NG C NH

ƯƠ

Ữ Ả

Ữ

Ạ

CH

NG 5. ÔTÔMÁT Đ Y XU NG

ƯƠ

Ố

Ẩ

CH

NG 6. MÁY TURING

ƯƠ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

ộ ố ấ ề ề

ữ

 Khái ni m văn ph m ệ

ạ

 Khái ni m Ôtômát ệ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG

ƯỜ

Ạ Ọ

Ẵ

CH

NG 1. M Đ U

ƯƠ

Ở Ầ

TR

NG Đ I H C BÁCH KHOA ĐÀ N NG