Giáo trình Ki n trúc máy tính và H đi u hànhế ệ ề 1
Đ I H C ĐÀ N NGẠ Ọ Ẵ
TR NG Đ I H C BÁCH KHOA ƯỜ Ạ Ọ
KHOA CÔNG NGH THÔNG TINỆ
NGÔN NG HÌNH TH C & ÔTÔMÁT Ữ Ứ
Giáo trình Ki n trúc máy tính và H đi u hànhế ệ ề 2
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.ề ữ ạ
2. Cung c p các ph ng pháp phân ấ ươ
tích t 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.ữ ậ
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ớ ệ
Giáo trình Ki n trúc máy tính và H đi u hànhế ệ ề 3
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ƯỜ Ạ Ọ Ẵ
Gi i thi uớ ệ
Giáo trình Ki n trúc máy tính và H đi u hànhế ệ ề 4
CH NG 1. M Đ UƯƠ Ở Ầ
TR NG Đ I H C BÁCH KHOA ĐÀ N NGƯỜ Ạ Ọ Ẵ
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ế ệ ề 5
CH NG 1. M Đ UƯƠ Ở Ầ
TR NG Đ I H C BÁCH KHOA ĐÀ N NGƯỜ Ạ Ọ Ẵ
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
T p các ch cái ti ng vi tậ ữ ế ệ