Bài Giảng Ngôn Ngữ Hình Thức Và Otomat - Trường Đại Học Bách ...

Có thể bạn quan tâm

Trang chủ
Đăng ký
Đăng nhập
Liên hệ

Bài Giảng Mẫu

Tổng hợp bài giảng điện tử mầm non, mẫu giáo, tiểu học, trung học, đại học

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

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

174 trang | Chia sẻ: hienduc166 | Lượt xem: 1041 | Lượt tải: 0 download

Bạn đang xem trước 20 trang tài liệu Bài giảng Ngôn ngữ hình thức và Otomat - Trường Đại học Bách khoa Đà Nẵng, để xem tài liệu hoàn chỉnh bạn click vào nút TẢI VỀ ở trênử 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

File đính kèm:

Ngon ngu hinh thuc va otomat.ppt

Bài giảng liên quan

Bài giảng Ngôn ngữ lập trình C++
132 trang | Lượt xem: 1344 | Lượt tải: 0
Hội thi Rung chuông vàng
37 trang | Lượt xem: 597 | Lượt tải: 0
Tọa đàm ngày Nhà giáo Việt Nam 20-11
38 trang | Lượt xem: 520 | Lượt tải: 0
Tập huấn Tổ chức kiểm tra, đánh giá theo chuẩn kiến thức, kỹ năng
22 trang | Lượt xem: 617 | Lượt tải: 0
Bài thuyết trình: Phân tích đối thủ cạnh tranh của mạng di động Mobifone - Lâm Thị Dâng Thu
17 trang | Lượt xem: 745 | Lượt tải: 0
Chuyên đề Ứng dụng phương pháp dạy VBND bằng giáo án điệ tử trong chương trình Ngữ văn - Nguyễn Thị Dung
22 trang | Lượt xem: 755 | Lượt tải: 0
Bài giảng An toàn sinh học trong heo Farms Một nghĩa vụ kinh tế & đạo đức
85 trang | Lượt xem: 674 | Lượt tải: 0
Hội vui học - Phần 2: Kiến thức vô tận
65 trang | Lượt xem: 773 | Lượt tải: 0
Bài giảng Giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị
42 trang | Lượt xem: 392 | Lượt tải: 0
Bài thuyết trình Kỹ năng giao tiếp và truyền thông - Đinh Thị Nguyệt
10 trang | Lượt xem: 697 | Lượt tải: 0