intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Lý thuyết automata và ngôn ngữ hình thức - Bài 1

Chia sẻ: Le Van Vi | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST
Báo xấu
332
lượt xem 25
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ứng dụng của lý thuyết ngôn ngữ hình thức và automata:  Dùng trong xử lý từ vựng và cú pháp ngôn ngữ tự nhiên;  Dùng trong xây dựng ngôn ngữ lập trình ctd; Dùng trong nhận dạng (đối với những mẫu nhận dạng có cấu trúc);  Dùng trong tin sinh học (Bio-informatics);  Dùng trong tính toán phân tử (DNA Computing);  Dùng trong xử lý ảnh (nén ảnh Fractal,...);  Dùng trong công nghệ phần mềm ( mã hóa dữ liệu, mô hình hoá các hệ thống động, các tiến trình hệ thống…); Trong lĩnh vực trí tuệ nhân tạo…...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lý thuyết automata và ngôn ngữ hình thức - Bài 1

  1. Lý thuyết automata và ngôn ngữ hình thức Automata Grammar Ngôn ngữ GIẢNG VIÊN: TS. HÀ CHÍ TRUNG hình thức BỘ MÔN: KHMT KHOA CNTT, HVKTQS ĐT:0168.558.21.02 EMAIL: HCT2009@YAHOO.COM ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
  2. Bài 1. Nhập môn Theory of automata and formal languagues – TA&FL (AL) 2 MỤC ĐÍCH:  Trang bị những hiểu biết chung nhất về môn học;  Khái quát lại một số khái niệm, cơ sở toán học làm cơ sở học tập môn học. YÊU CẦU:  Về nhà, sinh viên phải hệ thống lại các kiến thức cơ sở về toán liên quan và kiến thức lập trình. ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
  3. Bài 1. Nhập môn TA&FL 3 1.1. Giới thiệu về môn học TA&FL 1.2. Yêu cầu với môn học 1.3. Tài liệu tham khảo môn TA&FL 1.4. Bổ túc một số khái niệm toán học 1.4.1. Tập hợp 1.4.2. Quan hệ 1.4.3. Phép chứng minh 1.4.4. Đồ thị và cây Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  4. Bài 1. Nhập môn TA&FL 4 1.1. Giới thiệu về môn học TA&FL 1.2. Yêu cầu với môn học 1.3. Tài liệu tham khảo môn TA&FL 1.4. Bổ túc một số khái niệm toán học 1.4.1. Tập hợp 1.4.2. Quan hệ 1.4.3. Phép chứng minh 1.4.4. Đồ thị và cây Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  5. 1.1. Giới thiệu về môn học TA&FL 5  Ngôn ngữ hình thức (Formal Languages) là môn học cơ sở của ngành công nghệ thông tin:  Turing, Post Church,... nghiên cứu xây dựng mô hình toán học cho các máy tính toán (30,40th–XXc.);  Chomsky với mục đích xây dựng mô hình toán cho ngôn ngữ tự nhiên (50th–XXc.).  Môn học trang bị cho người học những kiến thức cơ bản về thuật toán, ngôn ngữ thuật toán, các kỹ thuật xây dựng chương trình, xây dựng các hệ thống tự động và phương pháp tư duy liên quan đến khoa học máy tính.  Kiến thức về ngôn ngữ hình thức và automat là nền tảng cho nhiều lĩnh vực của khoa học máy tính và CNTT. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  6. 1.1. Giới thiệu về môn học TA&FL 6  Ứng dụng của lý thuyết ngôn ngữ hình thức và automata:  Dùng trong xử lý từ vựng và cú pháp ngôn ngữ tự nhiên;  Dùng trong xây dựng ngôn ngữ lập trình ctd;  Dùng trong nhận dạng (đối với những mẫu nhận dạng có cấu trúc);  Dùng trong tin sinh học (Bio-informatics);  Dùng trong tính toán phân tử (DNA Computing);  Dùng trong xử lý ảnh (nén ảnh Fractal,...);  Dùng trong công nghệ phần mềm ( mã hóa dữ liệu, mô hình hoá các hệ thống động, các tiến trình hệ thống…);  Trong lĩnh vực trí tuệ nhân tạo… Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  7. 1.1. Giới thiệu về môn học TA&FL 7  Nội dung chính của môn học TA&FL: 1. Cơ sở toán học của môn TA&FL 2. Văn phạm và ngôn ngữ hình thức 3. Automata hữu hạn và ngôn ngữ hình thức 4. Văn phạm chính quy và các tính chất 5. Văn phạm phi ngữ cảnh 6. Pushdown automata (automata đẩy xuống) 7. Máy Turing 8. Phần bài tập lý thuyết và thực hành Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  8. Bài 1. Nhập môn TA&FL 8 1.1. Giới thiệu về môn học TA&FL 1.2. Yêu cầu với môn học 1.3. Tài liệu tham khảo môn TA&FL 1.4. Bổ túc một số khái niệm toán học 1.4.1. Tập hợp 1.4.2. Quan hệ 1.4.3. Phép chứng minh 1.4.4. Đồ thị và cây Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  9. 1.2. Một số yêu cầu với môn học 9  Kiến thức nền: Toán rời rạc (tập hợp, đồ thị, cây, quan hệ, phương pháp chứng minh,…);  các kiến thức toán liên quan;  khả năng lập trình (C, C++, C#,…)  Hình thức đánh giá:  Tổng số tiết: 45;  Hình thức thi: vấn đáp;  Điểm đánh giá: c.cần 10%, t.xuyên 20%, thi 70%;  Đồ án môn: Giải bài tập và viết chương trình. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  10. Bài 1. Nhập môn TA&FL 10 1.1. Giới thiệu về môn học TA&FL 1.2. Yêu cầu với môn học 1.3. Tài liệu tham khảo môn TA&FL 1.4. Bổ túc một số khái niệm toán học 1.4.1. Tập hợp 1.4.2. Quan hệ 1.4.3. Phép chứng minh 1.4.4. Đồ thị và cây Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  11. 1.3. Tài liệu môn học 11 1. Bài giảng của giảng viên. 2. Nguyễn Gia Định. Lý thuyết ngôn ngữ hình thức và ôtômát. Đại học khoa học Đại học Huế - 2004. 3. Nguyễn Văn Xuất. Giáo trình Automata, ngôn ngữ hình thức và nguyên lý chương trình dịch - HVKTQS – 2004. 4. Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ hình thức – Nhà xuất bản Đại học quốc gia Tp. Hồ Chí Minh – 2002. 5. John E. Hopcropft, Rareev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition) -Addison-Wesley.-2001. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  12. Bài 1. Nhập môn TA&FL 12 1.1. Giới thiệu về môn học TA&FL 1.2. Yêu cầu với môn học 1.3. Tài liệu tham khảo môn TA&FL 1.4. Bổ túc một số khái niệm toán học 1.4.1. Tập hợp 1.4.2. Quan hệ 1.4.3. Phép chứng minh 1.4.4. Đồ thị và cây Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  13. 1.4.1. Tập hợp 13 ĐN 1.1: Tập hợp là một nhóm các đối tượng rời rạc và không có sự lặp lại. Ví dụ 1.1: D = {Mon, Tue, Wed, Thu, Fri, Sat, Sun}; - các phần tử là rời rạc - các phần tử không lặp lại Phần tử Hình thức biểu diễn tập hợp:  Liệt kê phần tử: D = {1, 2, 3}  Mô tả tính chất đặc trưng: D = { x | x là một ngày trong tuần} Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  14. 1.4.1. Tập hợp 14  ĐN 1.2: Tập rỗng, ký hiệu là  hoặc { }  ĐN 1.3: Tập hợp con (subset) oKý hiệu: A  B (Ngược lại: A  B ) o{ 1, 2, 4 }  { 1, 2, 3, 4, 5 } nhưng { 2, 4, 6 }  { 1, 2, 3, 4, 5 }  ĐN 1.4: Tập hợp bằng nhau oKý hiệu: A = B nếu ( x  A )  ( x  B ), (ngược lại: A  B ) o{ 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 }  { 2, 1 }  ĐN 1.5: Tập lũy thừa (power set) oKý hiệu: 2A oA = { 1, 2, 3 } thì 2A = {, {1}, {2}, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} } Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  15. 1.4.1. Tập hợp 15  Kết quả của một số phép toán sau đây trên các tập hợp là một tập hợp mới.  Phần bù (complement): A’ = { x | x  A }  Phép hợp (Union): A  B = { x | x  A hoặc x  B }  Phép giao (intersection): A  B = { x | x A và x  B }  Phép trừ (difference): A \ B = { x | x  A nhưng x  B }  Tích Đềcác: A x B = { (a,b) | a  A và b  B } Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  16. 1.4.1. Tập hợp 16  Ví dụ 1.2: Cho A = {1, 2} và B = {2, 3} o A  B = { 1, 2, 3 } o AB={2} o A\B={1} o A x B = { (1,2 ), (1, 3), (2, 2), (2, 3) } o 2A = { , {1}, {2}, {1, 2} } Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  17. Bài 1. Nhập môn TA&FL 17 1.1. Giới thiệu về môn học TA&FL 1.2. Yêu cầu với môn học 1.3. Tài liệu tham khảo môn TA&FL 1.4. Bổ túc một số khái niệm toán học 1.4.1. Tập hợp 1.4.2. Quan hệ 1.4.3. Phép chứng minh 1.4.4. Đồ thị và cây Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  18. 1.4.2. Quan hệ 18  ĐN 1.6: Cho các tập hợp A1, A2, ..., An. Một quan hệ (relations) n-ngôi trên các các tập hợp này là tập hợp con của tích Đềcác A1◦A2 ◦... ◦ An mà thỏa mãn một số tính chất nào đó. Các tập hợp A1, A2, ..., An được gọi là miền của quan hệ và n gọi là bậc của quan hệ.  Ví dụ 1.3: Cho R là một quan hệ gồm bộ 3 số nguyên (a, b, c) thỏa mãn a < b < c trên tập nguyên dương.  Ví dụ 1.4: Cho R là một quan hệ gồm bộ 2 số nguyên (a, b) thỏa mãn a ≡ b mod 3 trên tập nguyên dương. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  19. 1.4.2. Quan hệ 19  ĐN 1.7: Cho hai tập hợp A và B. Một quan hệ (relations) hai ngôi R giữa A và B là tập hợp chứa tất cả các tập hợp con của A × B mà thành phần thứ nhất A được gọi là miền xác định (domain) của R, còn B gọi là miền giá trị (range) của R.  Nếu miền xác định và miền giá trị cùng thuộc một tập hợp S, gọi là một quan hệ trên S. Nếu R là một quan hệ và (a,b) là một cặp trong R thì ta viết aRb. S R( A  B ) = aRb miền xác định (domain)  miền giá trị (range) Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  20. 1.4.2. Quan hệ 20  Các tính chất của quan hệ:  Phản xạ (reflexive): nếu aRa là đúng với aS  Đối xứng (symmetric): nếu aRb thì bRa  Bắc cầu (transitive): nếu aRb và bRc thì aRc  Ví dụ 1.5: cho S = {0, 1, 2, 3} o Quan hệ ‘thứ tự nhỏ hơn’: L = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) } o Quan hệ ‘bằng’: E = { (0, 0), (1, 1), (2, 2), (3, 3) } o Quan hệ ‘chẵn lẻ’: P = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)} o Tính chất: L không là quan hệ phản xạ hay đối xứng, E và P mang tính phản xạ, đối xứng và bắc cầu Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2