Lý thuyết otomat – Msc Võ Huỳnh Trâm

Lý thuyết otomat – Msc Võ Huỳnh Trâm

Tài liệu Lý thuyết otomat – Msc Võ Huỳnh Trâm là tài liệu cơ bản về otomat bằng tiếng Việt. Tài liệu gồm 8 chương, kèm theo đó là bài tập của từng chương:

Chương 1: BỔ TÚC TOÁN

Trong chương này, chúng ta sẽ nhắc lại một cách khái quát các thuật ngữ và kiến thức toán học sẽ được dùng đến trong suốt giáo trình. Đó là các kiến thức liên quan đến đồ thị, cây, tập hợp, quan hệ và một vài phương pháp chứng minh toán học thông thường. Nếu các khái niệm này là mới đối với bạn, bạn nên xem lại một cách cẩn thận. Ngược lại, nếu chúng không là mới, bạn có thể đọc lướt nhanh qua chương này, nhưng hãy chắc chắn rằng mình đã nắm rõ về chúng.

Sau chương này, học viên có thể :

  • Xác định tập hợp và các phép toán cơ bản trên tập hợp
  • Định nghĩa một quan hệ, lớp quan hệ và các tính chất của quan hệ.
  • Xác định quan hệ tương đương và phép bao đóng.
  • Chứng minh một phát biểu toán học theo phương pháp quy nạp.
  • Nắm vững các khái niệm về đồ thị và cây.

Chương 2: NGÔN NGỮ VÀ SỰ PHÂN CẤP CHOMSKY

Chương này trình bày quan niệm hình thức về ngôn ngữ và khái niệm về các công cụ dùng để mô tả một tập hữu hạn ngôn ngữ có hiệu quả – đó là văn phạm và ôtômát. Đây là những công cụ có định nghĩa toán học chặt chẽ được nghiên cứu kỹ càng và đã trở thành một thành phần chủ yếu của lý thuyết ngôn ngữ hình thức. Để tiếp thu tốt nội dung của chương này, sinh viên cần có một số các kiến thức liên quan về chuỗi, ký hiệu, từ trong các ngôn ngữ tự nhiên như tiếng Việt, tiếng Anh; cấu trúc cú pháp của các chương trình máy tính viết bằng một số ngôn ngữ lập trình cơ bản nhhư Pascal, C…

Sau chương này, học viên cần nắm vững các khái niệm sau :

  • Cấu trúc ngôn ngữ tự nhiên cũng như ngôn ngữ lập trình.
  • Các phép toán cơ bản trên chuỗi, ngôn ngữ
  • Cách thức biểu diễn ngôn ngữ
  • Cách phân loại văn phạm theo quy tắc của Noam Chomsky
  • Xác định các thành phần của một văn phạm.
  • Mối liên quan giữa ngôn ngữ và văn phạm.

Chương 3: ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY

Trong chương này, ta sẽ nghiên cứu một loại “máy trừu tượng” gọi là ôtômát hữu hạn. Chúng là công cụ dùng đoán nhận một lớp ngôn ngữ khá đơn giản gọi là lớp ngôn ngữ chính quy. Trước hết, hai dạng của ôtômát hữu hạn sẽ lần lượt được trình bày và có sự chứng minh rằng chúng tương đương nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó, ta sẽ đề cập đến các biểu thức chính quy – một phương tiện khác để xác định ngôn ngữ và ta lại thấy rằng lớp ngôn ngữ do các ôtômát hữu hạn chấp nhận chính là lớp ngôn ngữ chính quy. Phần tiếp theo của chương sẽ đề cập đến mối quan hệ giữa cơ chế ôtômát và các biểu thức chính quy dùng ký hiệu cho ngôn ngữ. Cuối chương này, một vài ứng dụng cụ thể của ôtômát hữu hạn sẽ được trình bày.

Kết thúc chương này, học viên cần nắm vững :

  • Khái niệm ôtômát hữu hạn, các thành phần, các dạng và sự khác biệt cơ bản giữa hai dạng.
  • Cách thức chuyển đổi tương đương từ dạng đơn định sang không đơn định và ngược lại.
  • Viết biểu thức chính quy ký hiệu cho tập ngôn ngữ chính quy.
  • Mối liên quan giữa ôtômát hữu hạn và biểu thức chính quy.
  • Vẽ sơ đồ chuyển trạng thái (đơn định hoặc không đơn định) từ một biểu thức chính quy.
  • Tìm các ứng dụng thực tế khác từ mô hình ôtômát hữu hạn.

Chương 4: VĂN PHẠM CHÍNH QUY VÀ CÁC TÍNH CHẤT

Trong chương này, ta sẽ đề cập đến lớp văn phạm chính quy (dạng văn phạm tuyến tính trái hoặc phải) – một phương tiện khác để xác định ngôn ngữ và ta lại thấy rằng lớp ngôn ngữ do chúng sinh ra vẫn là lớp ngôn ngữ chính quy. Điều này được thể hiện bởi mối tương quan giữa văn phạm chính quy và ôtômát hữu hạn. Tiếp sau đó, ta sẽ nghiên cứu một số tính chất của lớp ngôn ngữ chính quy, cũng như các giải thuật xác định tập chính quy.

Cuối chương, sinh viên cần phải nắm vững :

  • Định nghĩa một biểu thức chính quy ký hiệu cho tập ngôn ngữ.
  • Mối liên quan giữa ôtômát hữu hạn và biểu thức chính quy.
  • Các tính chất của tập chính quy.
  • Xây dựng ôtômát từ biểu thức chính quy
  • Viết văn phạm chính quy sinh ra cùng tập ngôn ngữ được cho bởi ôtômát.

Chương 5: VĂN PHẠM PHI NGỮ CẢNH

Trong chương này, ta sẽ nghiên cứu một loại văn phạm khá quan trọng, gọi là văn phạm phi ngữ cảnh (CFG) và lớp ngôn ngữ mà chúng mô tả – ngôn ngữ phi ngữ cảnh(CFL). CFL, cũng như tập hợp chính quy, có nhiều ứng dụng thực tế rất quan trọng, đặc biệt trong việc biểu diễn ngôn ngữ lập trình. Chẳng hạn, CFG dùng hữu ích để mô tả các biểu thức số học trong các dấu ngoặc lồng nhau hay những cấu trúc khối trong ngôn ngữ lập trình (cấu trúc khối begin-end). Sau khi định nghĩa văn phạm phi ngữ cảnh, một số cách biến đổi văn phạm phi ngữ cảnh nhằm giản lược nó và đưa nó về một trong những dạng chuẩn sẽ được trình bày.

Cuối chương, học viên cần phải nắm vững:

  • Khái niệm CFG, xác định các thành phần của một CFG.
  • Nhận dạng được lớp ngôn ngữ mà một văn phạm CFG đặc tả.
  • Xây dựng các luật sinh cho một CFG đặc tả một lớp ngôn ngữ.
  • Các bước giản lược văn phạm CFG không chứa các giá trị vô ích.
  • Chuẩn hóa CFG về các dạng chuẩn Chomsky hoặc Greibach.
  • Ứng dụng bổ đề bơm cho CFL để chứng tỏ một ngôn ngữ không là ngôn ngữ phi ngữ cảnh.
  • Xác định một ngôn ngữ có thuộc lớp ngôn ngữ phi ngữ cảnh hay không theo các tính chất của CFL.
  • Kiểm tra tính rỗng, hữu hạn hoặc vô hạn của một CFL.

Chương 6: ÔTÔMÁT ĐẨY XUỐNG ( PDA : PUSHDOWN AUTOMATA)

Trong chương này, chúng ta khảo sát một dạng mô hình ôtômát khác, có khả năng nhận diện được lớp ngôn ngữ mà văn phạm phi ngữ cảnh sinh ra – ôtômát đẩy xuống (PDA) – với sự bổ sung thêm của Stack đóng vai trò như một bộ giữ nhớ trong quá trình ôtômát thực hiện các phép chuyển để nhận dạng ngôn ngữ. Sau đó, bổ đề bơm cho ngôn ngữ CFL và một số tính chất nhằm xác định tập ngôn ngữ phi ngữ cảnh cũng được giới thiệu. 

Cuối chương, học viên cần phải:

  • Thiết kế PDA chấp nhận một ngôn ngữ phi ngữ cảnh cho trước bằng Stack rỗng hay trạng thái kết thúc.
  • Chuyển một PDA chấp nhận ngôn ngữ bằng trạng thái kết thúc sang PDA chấp nhận ngôn ngữ bằng Stack rỗng và ngược lại.
  • Xây dựng NPDA chấp nhận ngôn ngữ sinh ra từ một CFG.
  • Viết văn phạm phi ngữ cảnh sinh ra lớp ngôn ngữ được chấp nhận bởi một NPDA cho trước.

Chương 7: MÁY TURING

Trong chương này, ta sẽ xét thêm một loại máy trừu tượng khác – máy Turing (TM – Turing Machines). Chúng có khả năng đoán nhận được lớp ngôn ngữ lớn hơn lớp ngôn ngữ phi ngữ cảnh. Đây còn là một mô hình của sự tính toán, mô hình của các thủ tục hiệu quả, là nền tảng cho quá trình xử lý của máy tính hiện đại, được giới thiệu bởi Alan Turing vào năm 1936. Nhờ đó, các khái niệm về “sự tính được”, “sự giải được” được xác định một cách rõ ràng trên cơ sở sự xuất hiện của một số hàm không tính được, các bài toán không giải được.

Cuối chương, học viên cần phải nắm vững:

  • Khái niệm TM, định nghĩa và các thành phần.
  • Các kỹ thuật thiết kế TM.
  • Một số biến dạng TM từ mô hình chuẩn.
  • Xây dựng TM dùng nhận dạng ngôn ngữ hoặc tính toán các hàm số nguyên đơn giản được biểu diễn trong hệ nhất phân.
  • Các tính chất của lớp ngôn ngữ được chấp nhận bởi TM.

Chương 8: ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ CẢNH

Trong chương này, chúng ta xét thêm một loại ôtômát, không mạnh bằng máy Turing, được gọi là ôtômát tuyến tính giới nội (Linear Bounded Automata – LBA). Đồng thời cũng xét thêm lớp văn phạm tương ứng với nó, là lớp văn phạm L1 hay còn gọi là văn phạm cảm ngữ cảnh, lớp văn phạm nằm giữa lớp văn phạm L0 và văn phạm phi ngữ cảnh L2. Từ đó ta hoàn thành sự phân cấp các ngôn ngữ thành 4 cấp, gọi là sự phân cấp Chomsky.

Cuối chương, học viên cần phải nắm vững:

  • Khái niệm LBA, định nghĩa và các thành phần.
  • Sự tương đương giữa LBA và văn phạm cảm ngữ cảnh.
  • Mối tương quan giữa các lớp ngôn ngữ.

Link tải tài liệu: Mediafire

Have fun!

- Trang hỗ trợ getlink: Click Here
- Các bạn nên dùng Winrar bản mới nhất để giải nén file tải về hoặc dùng phần mềm tạo ổ ảo như Virtual Clonedrive để mở file .iso nhé!
- Mọi thắc mắc, giao lưu, hỏi đáp, các bạn vui lòng nhắn với mình qua biểu tượng chat phía dưới góc phải màn hình hoặc Zalo: 0886.311.622 nhé!
Chúc các bạn thành công!
 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *