VĂN PHẠM CHÍNH QUY VÀ CÁC TÍNH CHẤT Nội dung chính : 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. | Chương IV Văn phạm chính quy và các tính chất CHƯƠNG Iv VĂN PHẠM CHÍNH QUY VÀ CÁC TÍNH CHẤT Nội dung chính 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. Mục tiêu cần đạt 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. Kiến thức cơ bản Để tiếp thu tốt nội dung của chương này sinh viên cần nắm vững các thành phần tổng quát của một văn phạm cấu trúc các dạng luật sinh hiểu biết về ngôn ngữ tự nhiên cơ chế đoán nhận ngôn ngữ từ ôtômát hữu hạn và cách phát sinh một lớp ngôn ngữ thông qua biểu thức chính quy . Tài liệu tham khảo 1 . Rayward-Smith - A First course in Formal Language Theory Second Editor - McGraw-Hill Book Company Europe - 1995 Chapter 3 Regular Language I 2 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 Chương 4 Văn phạm chính quy 3 From Wikipedia the free encyclopedia - Regular Grammar http wiki Regular grammar 51 Chương IV Văn phạm chính quy và các tính chất I. VĂN PHẠM CHÍNH QUY rg REGULAR GRAMMAR Như trong chương 3 ta đã biết lớp ngôn ngữ được chấp nhận bởi ôtômát hữu hạn được gọi là ngôn ngữ chính quy và chúng có thể được ký hiệu một cách đơn giản bằng việc dùng một biểu thức chính quy. Chương này giới thiệu một cách khác để mô tả ngôn ngữ chính quy thông qua cơ chế sản sinh ngôn ngữ - đó là văn phạm chính quy. Xét một định nghĩa cho .
