Giáo trình Ôtômát và ngôn ngữ hình thức: Phần 1 - Trường ĐH Công nghiệp Vinh

Giáo trình “Ôtômát và ngôn ngữ hình thức” theo hướng kết hợp ba mảng chính: lý thuyết ôtômát, ngôn ngữ hình thức và lý thuyết tính toán gồm những khái niệm, kiến thức cơ bản nhất với nhiều ví dụ minh hoạ, bỏ qua các chứng minh lý thuyết không thực sự cần thiết, nhằm tập trung tối đa thời gian cho việc giải các bài tập, ví dụ thực tiễn. Mời các bạn cùng tham khảo nội dung phần 1 dưới đây.
Nội dung trích xuất từ tài liệu:
Giáo trình Ôtômát và ngôn ngữ hình thức: Phần 1 - Trường ĐH Công nghiệp Vinh Ôtômát và ngôn ngữ hình thức TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP VINH KHOA CÔNG NGHỆ NGÀNH CÔNG NGHỆ THÔNG TIN NGUYỄN NGỌC THUẦN ÔTÔMÁT VÀ NGÔN NGỮ HÌNH THỨC Vinh, 2016 1 Ôtômát và ngôn ngữ hình thức LỜI NÓI ĐẦU Ôtômát và ngôn ngữ hình thức là lĩnh vực thuộc chuyên ngành Khoa học máy tính, chủ yếu dùng trong việc mô tả, hình thức hóa các dãy tính toán và điều khiển tự động, được phát sinh trong nhiều ngành khoa học khác nhau từ các hệ thống tính toán, ngôn ngữ học đến sinh học,. .... Ngày nay, các ngôn ngữ lập trình, các hệ thống máy tính, các quá trình xử lý thông tin và các quá trình tính toán nói chung đều được hình thức hoá thành các mô hình toán học mà lý thuyết ôtômát và ngôn ngữ hình thức là công cụ. Ôtômát và ngôn ngữ hình thức được áp dụng rộng rãi trong nhiều lĩnh vực khoa học và ứng dụng như: mô hình hoá, mô phỏng các hệ thống tính toán, các kỹ thuật dịch, thông dịch, trí tuệ nhân tạo, công nghệ tri thức, ... Nhằm đáp ứng nhu cầu giảng dạy, học tập và nghiên cứu cho các sinh viên ngành Công nghệ thông tin của trường Đại học Công nghiệp Vinh – là trường Đại học hoạt động theo hướng thực hành, chúng tôi biên soạn giáo trình “Ôtômát và ngôn ngữ hình thức” theo hướng kết hợp ba mảng chính: lý thuyết ôtômát, ngôn ngữ hình thức và lý thuyết tính toán gồm những khái niệm, kiến thức cơ bản nhất với nhiều ví dụ minh hoạ, bỏ qua các chứng minh lý thuyết không thực sự cần thiết, nhằm tập trung tối đa thời gian cho việc giải các bài tập, ví dụ thực tiễn. Giáo trình giới thiệu một cách hệ thống những khái niệm cơ bản và các tính chất chung của ôtômát và ngôn ngữ hình thức. Chương mở đầu trình bày các khái niệm cơ bản, các tính chất quan trọng của các cấu trúc đại số, logic mệnh đề,... làm cơ sở cho các chương sau. Chương 2, giới thiệu về Văn phạm và các ngôn ngữ hình thức. Lý thuyết Ôtômát, những khái niệm cơ sở và các hoạt động của Ôtômát được đề cập ở Chương 3. Những vấn đề liên quan đến tập chính qui, ngôn ngữ chính qui và ôtômát hữu hạn được trình bày chi tiết ở Chương 4. Chương 5, nghiên cứu các khái niệm cơ sở, mối quan hệ giữa các lớp ngôn ngữ và các tính chất rất quan trọng của ngôn ngữ phi ngữ cảnh, Ôtômát đẩy xuống. Sau mỗi Chương có các bài tập hệ thống hoá lại kiến thức và thông qua đó, học viên nắm bắt được các khái niệm cơ bản, các kiến thức chủ yếu của từng Chương và cuối cùng là để nâng cao sự hiểu biết về ôtômát và ngôn ngữ hình thức, đồng thời phát triển khả năng ứng dụng chúng trong nghiên cứu và triển khai ứng dụng Công nghệ thông tin. 2 Ôtômát và ngôn ngữ hình thức Mặc dù đã có nhiều cố gắng, nhưng tài liệu này chắc không tránh khỏi những thiếu sót. Chúng tôi rất mong nhận được các ý kiến, góp ý của các đồng nghiệp và bạn đọc để hoàn thiện hơn cuốn giáo trình Ôtômát và ngôn ngữ hình thức. Các ý kiến đóng góp xin được gửi về: Bộ môn CNTT, Khoa Công Nghệ, trường ĐHCN Vinh. Số 26, Đường Nguyễn Thái Học, Phường Đội Cung, Tp. Vinh, Tỉnh Nghệ An. Chủ biên TS. Nguyễn Ngọc Thuần 3 Ôtômát và ngôn ngữ hình thức MỤC LỤC Nội dung Trang Chương 1: Bổ túc – Các khái niệm cơ bản. 1 – 10 1.1 Tập hợp 1 1.2 Quan hệ và Đồ thi.̣ 3 1.3. Đa ̣i cương về ngôn ngữ. 7 1.4. Bài tâ ̣p: 10 Chương 2: Văn phạm và các ngôn ngữ hình thức 11 – 37 2.1 Văn phạm và các ngôn ngữ 11 Định nghĩa Văn phạm: Bộ 4 thành phần G = (∑,V, P, S). 12 2.2. Các dẫn xuất và và ngôn ngữ sinh bởi văn phạm 13 + Dẫn xuất 14 + Ngôn ngữ sinh. 15 + Văn phạm tương đương 15 + Bài toán thuận và Bài toán ngược. 16 - 21 2.3. Phân loại ngôn ngữ (Văn pha ̣m) của Chomsky 22 - 27 2.4. Tính đệ qui và tập đệ qui. 28 - 30 2.5. Các phép toán trên các ngôn ngữ. 31 – 35 2.6. Các ví dụ và bài tập. 36 – 37 Chương 3: Lý thuyết Ôtômát 38 - 57 3.1 Ôtômát hữu hạn 38 3.1.1 Hàm chuyển trạng thái và tính chất 40 3.1.2 Các phương pháp biểu diễn ôtômát 41 3.1.3 Ngôn ngữ đoán nhận được của ôtômát 42 3.2. Ôtômát hữu hạn không đơn định 44 3.3. Sự tương đương của ôtômát đơn định và không đơn định. 47 - 50 3.4. Cực tiểu hoá ôtômát hữu hạn. 51 – 55 3.5. Các ví dụ và Bài tập. 56 – 57 4 Ôtômát và ngôn ngữ hình thức Chương4: Tập chính qui và văn phạm chính qui 58 - 75 4.1 Các biểu thức chính qui. 58 4.2 Sự tương đương của các biểu thức chính qui 59 Định lý (Định lý Arden) 60 4.3 Ôtômát hữu hạn và biểu thức chính qui 62 4.3.1 Phương pháp đại số ứng dụng định lý Arden 63 - 66 4.3.2 Thiết lập ôtômát hữu hạn tương đ ...