Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 1 - ThS. Nguyễn Thị Thùy Linh

Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 1 Kiến thức cơ sở cung cấp cho người học những kiến thức như: Lý thuyết tập hợp; Các quan hệ; Đồ thị và cây. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 1 - ThS. Nguyễn Thị Thùy Linh TRƯỜNG ĐẠI HỌC ĐỒNG THÁP KHOA SƯ PHẠM TOÁN - TIN Giới thiệu BÀI GiẢNG MÔN HỌC • Lý thuyết ngôn ngữ hình thức và ôtômát đặt nền tảng mạnh mẽ trên lý thuyết tập hợp, hàm, ánh ÔTÔMÁT VÀ xạ, quan hệ và lý thuyết đồ thị. NGÔN NGỮ HÌNH THỨC • Kỹ thuật mô phỏng các quá trình làm việc tương tự trên máy tính. Biên soạn : Ths.Nguyễn Thị Thùy Linh E-mail : nttlinh@dthu.edu.vn 1 2 Mục tiêu NỘI DUNG MÔN HỌC• Nghiên cứu hai lý thuyết cơ sở trong lĩnh vực khoa học máy tính: – Lý thuyết về ôtômát: lý thuyết cơ bản cho việc nghiên cứu Chương 1: Kiến thức cơ sở các mô hình tính toán tự động để làm tiền đề cho sự phát triển dạng máy tính số như hiện nay. Chương 2: Ngôn ngữ, văn phạm và ôtômát. – Lý thuyết về ngôn ngữ hình thức (Formal languages): nền tảng cho việc thấu hiểu khái niệm về ngôn ngữ nói chung (cả Chương 3: văn phạm chính quy và Ôtômát hữu hạn ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên), và các vấn đề cơ bản về ngôn ngữ như cách xây dựng văn phạm sinh ra ngôn Chương 4: Văn phạm phi ngữ cảnh và Ôtômát đẩy xuống. ngữ (xây dựng văn phạm cho ngôn ngữ lập trình, cho quá trình phân tích cú pháp), dịch từ ngôn ngữ lập trình cấp cao Chương 5: Máy Turing. sang ngôn ngữ máy… – Hai khía cạnh này có mối liên quan mật thiết với nhau trong ứng dụng của khoa học máy tính. 3 4 1 Đánh giá môn học Chương 1: Kiến thức cơ sở• Thi tự luận cuối kỳ: hệ số 0.7 Kiến thức nền (nhắc lại) – Hình thức: Bài tập 1. Lý thuyết tập hợp. – Thời gian 90 phút, được sử dụng tài liệu 2. Các quan hệ.• Kiểm tra thường kỳ: hệ số 0.3 3. Đồ thị và cây. – Kiểm tra bài tập tại lớp (50%) – Tự học, tự nghiên cứu (50%) 5 6 Các ký pháp về tập hợp Các ký pháp về tập hợp (tt) • x là phần tử của A, ta viết x  A. • x không là phần tử của A, ta viết x  A. • Nếu mọi phần tử của A đều là phần tử của B, ta viết A  B. • A = B  A  B và B  A. 7 8 2 Các phép toán trên các tập hợp Các phép toán trên các tập hợp (tt) • Thí dụ : Cho A = {1, 2} và B = {2, 3}• A  B = {x| x  A hoặc x  B} • A  B = {1, 2, 3}• A  B = {x| x  A và x  B} • A  B = {2}• A – B = {x| x  A và x  B} • A – B = {1}• A x B, tích Đềcác của A và B, là tập hợp có thứ tự • A x B = {(1, 2), (1, 3), (2, 2), (2, 3)} (a, b) sao cho a  A và b  B • 2A = {, {1}, {2}, {1, 2}} • Lưu ý: Nếu A và B lần lượt có n và m phần tử thì• 2A, tập lũy thừa của A, đó là tập hợp mọi tập con A x B có n x m phần tử của A. 2A có 2n phần tử 9 2B có 2m phần tử 10 Các quan hệ Các tính chất của quan hệ• ĐN: Cho 2 tập hợp A và B. Một quan hệ Ta nói một quan hệ R trên tập A là: giữa A và B, ký hiệu R, ...