BÀI T P L N: Ậ Ớ
LÝ THUY T NGÔN NGẾ Ữ
NG D NG C A VĂN PH M Ứ Ụ Ủ Ạ
VÀ AUTOMATA
THÀNH VIÊN NHÓM 4 CÙNG TH C HI N:Ự Ệ
1. NGUY N NG C TÂMỄ Ọ
2. NGUY N TH SENỄ Ị
3. NGUY N TH SÁNGỄ Ị
4. NGUY N TH H NG TH MỄ Ị Ồ Ắ
CÙNG S H NG D N C A Ự ƯỚ Ẫ Ủ
TH.s TR N XUÂN SANGẦ
GIÁO VIÊN CHUYÊN MÔN
PH N I:Ầ
NG D NG C A AUTOMATA Ứ Ụ Ủ
H U H N TRONG VI C PHÂN Ữ Ạ Ệ
TÍCH T V NG M R NGỪ Ự Ở Ộ
Applications of finite Automata
Repres enting large Vocabularies
GI I THI UỚ Ệ
Cách dùng otomat h u h n đ mô t m t lo t ữ ạ ể ả ộ ạ
các t v ng là m t k thu t đã đ c kh ng đ nh. ừ ự ộ ỹ ậ ượ ẳ ị
Có th ng d ng mang tính truy n th ng. Nó ể ứ ụ ề ố
đ c tìm th y trong c u trúc l nh n i mà ôtômat ượ ấ ấ ệ ơ
có th đ c s d ng đ làm m u và th c hi n ể ượ ử ụ ể ẫ ự ệ
nh ng phân tích t v ng h c mang tính hi u ữ ừ ự ọ ệ
qu . ng d ng c a ôtmat h u h n đ gi i quy t ả Ứ ụ ủ ữ ạ ể ả ế
m t vài v n đ đ c bi t trong vi c x lý ngôn ộ ấ ề ặ ệ ệ ử
ng t nhiên là khá ph bi n. Tuy nhiên, ý t ng ữ ự ổ ế ưở
gói g n các “t v ng m r ng” vào otomat đ n ọ ừ ự ở ộ ơ
đ nh và nhi u ng d ng c a nó d ng nh còn ị ề ứ ụ ủ ườ ư
mang tính m i m .ớ ẻ
C s đ thúc đ y cho nghiên c u này là m t ơ ở ể ẩ ứ ộ
ch ng trình ki m tra l i chính t áp d ng cho ươ ể ỗ ả ụ
h u h t các ngôn ng . Cho ví d , ch ng ầ ế ữ ụ ươ
trình ki m tra chính t mà chúng ta đ c p có ể ả ề ậ
th x lý kho ng 30.000 t m i giây, v i ể ử ả ừ ỗ ớ
automat h n 200.000 t đ t v a khít vào 124 ơ ừ ặ ừ
kbytes b nh .ộ ớ