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
Nội dung trích xuất từ tài liệu:
NGÔN NGỮ HÌNH THỨC & ÔTÔMÁT ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TINNGÔ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 1 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG Giới thiệu Mục tiêu giáo trình1. 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 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 Giới thiệu Nội dung giáo trìnhCHƯƠNG 1. MỞ ĐẦUCHƯƠNG 2. ÔTÔMÁT HỮU HẠNCHƯƠNG 3. BIỂU THỨC VÀ VĂN PHẠM CHÍNH QUICHƯƠNG 4. VĂN PHẠM VÀ NGÔN NGỮ PHI NGỮ CẢNHCHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNGCHƯƠNG 6. MÁY TURING Giáo trình Kiến trúc máy tính và Hệ điều hành 3 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 4 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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 Giáo trình Kiến trúc máy tính và Hệ điều hành 5 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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 Ví dụ: 0110 là xâu trên bộ chữ {0,1} 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 Ký hiệu: độ dài xâu x là |x| Giáo trình Kiến trúc máy tính và Hệ điều hành 6 Ví dụ: |01110|=5 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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 Ký hiệu: ε, |ε|=0- Tập tất cả các xâu trên V là V*, {ε}⊆V* V+ =V *-{ε} V*: tập vô hạn đếm được Ví dụ: V={a,b}V*={ε,a,b,aa,bb,ab,ba,…} Giáo trình Kiến trúc máy tính và Hệ điều hành 7 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. Một số vấn đề về ngôn ngữ1.1. Xâu- Các phép toán trên xâu• 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ết x trước, rồi đến y sau chứ không có dấu cách. Ví dụ: x=01 y=0110 Giáo trình Kiến trúc máy tính và Hệ điều hành 8 xy=010110 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. Một số vấn đề về ngôn ngữ1.1. Xâu• Đảo ngược xâu x (xr): xâu được viết theo thứ tự ngược lại của xâu x Ví dụ: x=0101 xr =1010 Chú ý: εr= ε, 1r =1- Xâu x mà x=xr thì x là xâu hình tháp (xâu đối xứng) Ví dụ: x=0110 Giáo trình Kiến trúc máy xr=0110, tính và Hệ điều hành x: xâu hình tháp9 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. Một số vấn đề về ngôn ngữ1.1. Xâu• Lũy thừa xâu x (xn): xâu nhận được bằng cách ghép tiếp chính xâu x n lần. xn = x.x.x...x (n lần x) x0 = ε với mọi xâu x Ví dụ: x=01 x3 =010101 10= ε Giáo trình Kiến trúc máy tính và Hệ điều hành 10 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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 tập hợp: ∩(giao), ∪(hợp), -(hiệu), bù• Ghép tiếp 2 ngôn ngữ Giáo trình Kiến trúc máy tính và Hệ điều hành 11 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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}• Phép bù: GiáoL=V trình Kiến-trúc * Lmáy tính và Hệ điều hành 12 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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)} x.x=x2; x.x.x=x3; x0=ε; xi=xi-1x L0={ε}; Li=Li-1.L- L*=L0∪L ∪L Giáo 1trình Kiế2n∪…∪; LH+ệ=L trúc máy tính và ∪L2∪…∪ điều1hành 13 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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ệt kê: ngôn ngữ có số xâu là hữu hạn và có thể xác định được. Ví dụ: ngôn ngữ là các số tự nhiên nhỏ hơn 20 và lớn hơn 12 L={13, 14, 15, 16, 17, 18, 19} Giáo trình Kiến trúc máy tính và Hệ điều hành 14 TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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 sử dụng tân từ P(x): ngôn ngữ 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. L={x/ (x∈ R) và (x TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 1. MỞ ĐẦU1. 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ữ- Đối với ngôn ngữ tự nhiên: văn phạm là hệ thống ngữ pháp.- Đối với ngôn ngữ lập trình: văn phạm là qui tắc cú pháp v ...