Bài giảng Ngôn ngữ hình thức và Otomat - Trường Đại học Bách khoa Đà Nẵng

ử sản xuất đơn vịcặp (S,B), có Bab và Bbb nên thêm: Sab |bbcặp (A,B), có Bab và Bbb nên thêm: Aab |bbcặp (B,A), có Aa nên thêm: Ba	142Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNHTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGDạng chuẩn của văn phạm phi ngữ cảnhKhử 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	Bab |bb | a143Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNHTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGDạng chuẩn của văn phạm phi ngữ cảnhKhử sản xuất đơn vịBài tập: khử sản xuất đơn vị cho văn phạm sau:S0A | 1 A | A 	AS | 0 | 1EE+T | T	TT*F | F	F(E) | a	144Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống (PDA)Ngôn ngữ được đoán nhận PDASự tương đương giữa PDA và văn phạm phi ngữ cảnhÔtômat đẩy xuống đơn định 145Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG01011Ôtômat đẩy xuống	(Push Down Automat - PDA)1.1. Mô tả Băng vàoqBộ điều khiểnĐầu đọcNgăn xếp146Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.1. Mô tả 	Tại một thời điểm bộ điểu khiển: Trạng thái q Đọc một ký hiệu trên băng vào (: k0 đọc) Nhìn ký hiệu ở đỉnh ngăn xếp xác định trạng thái tiếp theo và quyết định hành động liên quan đến ngăn xếp147Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.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 Đọc xong xâu vào và ngăn xếp rỗng148Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.2. Định nghĩa: M(Σ, Q, , z, δ, q0, F)	Σ: bộ chữ vào	Q: tập hữu hạn các trạng thái	q0  Q: trạng thái đầu	F  Q: tập các trạng thái kết thúc	  : tập ký hiệu trên ngăn xếp	z   : ký hiệu đầu tiên ở đỉnh ngăn xếp	δ: hàm chuyển trạng thái dạng δ(q,a,x)={(p, )} Với q,p  Q, a  Σ{}, x ,   *149Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.2. Định nghĩa: M(Σ, Q, , z, δ, q0, F)	δ: hàm chuyển trạng thái dạng δ(q,a,x)={(p, )} Với q,p  Q, a  Σ{}, x ,   *X: ký hiệu ở đỉnh ngăn xếp: chuỗi ký hiệu thay thế x ở đỉnh ngăn xếp= : ký hiệu x trên đỉnh ngăn xếp được lấy ra=x: ngăn xếp không thay đổi.=yz: lấy x ra, đẩy z vào, đẩy y vào.150Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.2. Định nghĩaVí dụ: Otomát đẩy xuống đoán nhận các xâu anbn 	với n>=0: 	M(Σ, Q, , z, δ, q0, F)	Σ: {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	z : ký hiệu đầu tiên ở đỉnh ngăn xếp	151Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.2. Định nghĩa	δ(q0,a,z)={(q1,1z )}	δ(q0,,z)={(q3, )}	δ(q1,a,1)={(q1,11)}	δ(q1,b,1)={(q2,)}	δ(q2,b,1)={(q2, )}	δ(q2,,z)={(q3, )}152Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.3. Biểu diễn PDA bằng biểu đồ dịch chuyển Các trạng thái được đặt trong các vòng trònTrạng thái đầu có dấu “>” gắn phía trướcTrạng thái kết thúc đặt trong vòng tròn képδ(q,a,x)=(p, ): từ trạng thái q sang trạng thái p có nhãn a, x|Ký hiệu đầu đỉnh ngăn xếp qui ước là z	153Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.3. Biểu diễn PDA bằng biểu đồ dịch chuyển Ví dụ: vẽ ôtômat PDA đoán nhận xâu anbn với n>=0a,z|1za,1|11b,1|,z|b,1|,z|q0 q1 q2 q3 154Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.4. Cấu hình của PDA 	Cấu hình của PDA là bộ (q,w, ):q: trạng tháiw: phần xâu vào sẽ đọc: nội dung của ngăn xếp (đỉnh-đáy: trái-phải) 155Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống1.4. Cấu hình của PDA 	Ví dụ: Cấu hình của PDA ở ví dụ trước đoán nhận xâu: aaabbb(q0,aaabbb,z) |- (q1,aabbb,1z) |- (q1,abbb,11z) |- (q1,bbb,111z) |- (q2,bb,11z) |- (q2,b,1z) |- (q2,,z) |- (q3,,) Có nghĩa (q0,aaabbb,z) |-* (q3,,) : xâu vào được đoán nhận156Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.1. Đoán nhận bởi trạng thái kết thúc Ngôn ngữ L được PDA M đoán nhận bởi trạng thái kết thúc là:	L(M)={w | (q0,w,z ) |-* (qf ,,)} với qf F, *157Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.2. Đoán nhận bởi ngăn xếp rỗng Ngôn ngữ L được PDA M đoán nhận bởi ngăn xếp rỗng :	L(M)={w | (q0,w,z ) |-* (qk ,,)} với qk Q158Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDABài tập: vẽ PDA đoán nhận xâu x là: anbmcm với n,m>=0 anbmcn với n,m>0 Các cặp dấu () tương thích Số nhị phân có số chữ số 0 bằng số chữ số 1 biểu thức số học ở dạng hậu tố có 1 số hạng aSố nhị phân có số chữ số 0 gấp đôi số chữ số 1 và xâu khác  159Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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	Cho PDA M(Σ, Q, , z, δ, q0) đoán nhận bởi ngăn xếp rỗng thành M’(Σ, Q’, ’, z’, δ’, q0’, F) đoán nhận bởi trạng thái kết thúc có:Q’=Q{q0’,qf}F={qf}’= {z’}160Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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δ’ được xác định:Mq0 q0’,z’|zz’ qf ,z’| ,z’| ,z’| 161Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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ụ: q1 q0 a,z|1z a,1|11b,1|,z|162Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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ụ: q1 q0 a,z|1z a,1|11b,1|,z|,z’|zz’qf q0 q0’q1 a,z|1za,1|11b,1|,z|,z’|163Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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ụ: q1 q0 a,z|1za,1|11b,1|,z|164Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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ụ: (ab)n với n>0q1 q0 q1 a,z|zzb,z|a,z|zzq3,z|165Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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 	Cho PDA M(Σ, Q, , z, δ, q0, F) đoán nhận bởi ngăn xếp rỗng thành M’(Σ,Q’,’, z’, δ’,q0’) đoán nhận bởi trạng thái kết thúc có:Q’=Q{q0’,qk}’= {z’}166Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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:Mq0 ,z’|zz’ qk ,’| q0’,’| ,’| 167Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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ụ: anbm với n,m>=0q1q0a,z|1z a,1|11b,z|1z b,1|11b,1|11,z|z168Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGNgôn ngữ được đoán nhận bởi PDA2.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ụ: anbn với n>=0b,1|11a,z|1z a,1|11b,z|1z b,1|11qf q1q0,z| ,1|,z|z,z| ,1|169Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGÔtômat đẩy xuống đơn địnhÔtômát đẩy xuống thỏa mãn: (q,a,X) chỉ chứa một giá trị duy nhất(q,a,X) không rỗng thì (q,,X) phải rỗng170Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGSự tương đương giữa PDA và văn phạm phi ngữ cảnh4.1. Chuyển văn phạm phi ngữ cảnh thành PDABộ 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ệt171Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGSự tương đương giữa PDA và văn phạm phi ngữ cảnh4.2. Chuyển PDA thành văn phạm phi ngữ cảnhBộ 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ệt172Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 6. MÁY TURINGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGMộ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ệt173Giáo trình Kiến trúc máy tính và Hệ điều hànhCHƯƠNG 6. MÁY TURINGTRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNGMộ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ệt174Giáo trình Kiến trúc máy tính và Hệ điều hành