TAILIEUCHUNG - Bài giảng Lý thuyết tính toán: Bài 4 - Phạm Xuân Cường

Bài giảng Lý thuyết tính toán: Bài 4 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về biểu thức chính quy; khái niệm của biểu thức chính quy; định nghĩa hình thức; sự tương đương với ôtômat hữu hạn; ôtômat hữu hạn không đơn định suy rộng (GNFA); . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LÝ THUYẾT TÍNH TOÁN BÀI 4 BIỂU THỨC CHÍNH QUY Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@ Nội dung bài giảng 1. Khái niệm 2. Định nghĩa hình thức 3. Sự tương đương với Ôtômat hữu hạn 1 Khái niệm Khái niệm Biểu thức chính quy Sử dụng các toán tử chính quy để biểu diễn một biểu thức mô tả ngôn ngữ Ví dụ 0 1 0 Tất cả các xâu bắt đầu bằng 1 ký tự 0 hoặc 1 và sau đó là một số nào đó các ký tự 0 Vai trò của Biểu thức chính quy Là một phương pháp mạnh để mô tả 1 mẫu văn bản nào đó Trong một số ngôn ngữ lập trình đều ứng dụng kỹ thuật mô tả mẫu bằng biểu thức chính quy Regular Expression 2 Định nghĩa hình thức Định nghĩa hình thức của biểu thức chính quy Ta nói R là một biểu thức chính quy nếu R là 1. a với a là ký hiệu nào đó trọng bộ chữ Σ 2. ε 3. Ø 4. R1 R2 trong đó R1 và R2 là các biểu thức chính quy 5. R1 R2 trong đó R1 và R2 là các biểu thức chính quy 6. R1 trong đó R1 là một biểu thức chính quy 3 Độ ưu tiên của các toán tử chính quy Toán tử sao có độ ưu tiên cao nhất ab a b 6 ab Toán tử ghép tiếp có độ ưu tiên cao hơn toán tử hợp a b c a b c 6 a b c Một số ký hiệu khác - Hoặc Union ab c ab c 6 a b c - Sao a a a - 1 hoặc nhiều a aa a - Tùy chọn a a ε a ε a 4 Ví dụ về độ ưu tiên toán tử chính quy aab caab caa aab caab caa d ab cd d ab cd 5 Ví dụ về độ ưu tiên toán tử chính quy aab caab caa aab caab caa aab caab caa aab caab caa d ab cd d a b c d d ab cd d a b c d 6 Ví dụ biểu thức chính quy Giả thiết sử dụng bộ chữ Σ 0 1 1. 0 10 w w chỉ có một ký hiệu 1 2. Σ 1Σ w w có ít nhất một ký hiệu 1 3. Σ 001Σ w w có chứa xâu con 001 4. 1 01 w sau mỗi ký hiệu 0 trong w sẽ có ít nhất 1 ký hiệu 1 5. ΣΣ w w là xâu có độ dài là một số chẵn 6. 01 10 01 10 7 Ví dụ biểu thức chính quy 7. 0Σ 0 1Σ 1 0 1 w w bắt đầu và kết thúc bởi cùng 1 ký hiệu 8. 0 ε 1 01 1 9. 0 ε 1 ε ε 0 1 01 10. 1 Ø Ø Ghép tập trống với bất cứ tập nào cũng sinh ra tập trống 11. Ø ε 12. Ø 01 01 8 Sự tương đương với Ôtômat hữu hạn Ngôn ngữ của biểu thức chính quy Mỗi biểu thức chính quy R đều mô tả một

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Biểu thức chính quy
• Ôtômat hữu hạn
• Toán tử chính quy
• Ngôn ngữ của biểu thức chính quy
• giáo trình lý thuyết tính toán
• tài liệu về lý thuyết tính toán
• học lý thuyết tính toán
• tự học lý thuyết tính toán
• Tổng quan lý thuyết tính toán
• Khái niệm ngôn ngữ
• Khái niệm văn phạm
• Các phép toán trên ngôn ngữ
• Cơ sở toán học
• Cơ sở thuật toán
• Lý thuyết khoa học máy tính
• Văn phạm phi ngữ cảnh
• Quy dẫn
• Bài toán không quyết định được
• Quy dẫn thông qua lịch sử tính toán
• Bài toán PCP
• Quy dẫn ánh xạ
• Ôtômat đẩy xuống
• Mô hình tính toán
• Ngôn ngữ không phi ngữ cảnh
• Ngôn ngữ phi ngữ cảnh
• Định nghĩa giải thuật
• Bài toán của Hilbert
• Luận đề Church Turing
• Ngôn ngữ quyết định được
• Bài toán quyết định được
• Ngôn ngữ chính quy
• Bài toán dừng
• Máy Turing vạn năng
• Phương pháp chéo hóa
• Ngôn ngữ vạn năng
• Bài giảng Lý thuyết hạch toán kế toán
• Lý thuyết hạch toán kế toán
• Hệ thống phương pháp hạch toán kế toán
• Phương pháp chứng từ
• Phương pháp tính giá
• Phương pháp tổng hợp cân đối
• Quy hoạch tuyến tính
• Lý thuyết quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• Quy hoạch tuyến tính tổng quát
• Quy hoạch tuyến tính chính tắc
• Bài toán vận tải
• Tính chất của ngôn ngữ chính quy
• Ngôn ngữ không chính quy
• Nhận biết ngôn ngữ không chính quy
• Thiết kế ôtômat hữu hạn
• Ôtômat hữu hạn không đơn định
• Toán tử chính quy với NFA
• Nondeterministic Finite State Automaton (NFA)
• Toán học cơ sở
• Máy trừu tượng
• Biểu diễn ngôn ngữ
• Cấu trúc rời rạc
• Văn phạm và ô tô mát
• Kiến thức cơ bản về ngôn ngữ
• Phương pháp phân tích từ vựng
• Phân tích cú pháp
• Automat hữu hạn
• Accepter hữu hạn đơn định
• Accepter hữu hạn không đơn định
• Rút gọn số trạng thái
• Văn phạm chính quy
• Quan hệ ngôn ngữ và biểu thức chính quy
• Ngôn ngữ lập trình
• Biến đổi văn phạm
• Dạng chuẩn quan trọng
• Giải thuật thành viên
• Tập hợp
• Đồ thị
• Boolean logic
• Quan hệ tương đương
• Độ dài dẫn xuất
• Bổ đề Bơm (Pumping Lemma)
• Văn phạm nhập nhằng
• Dạng chuẩn tắc Chomsky
• Quy tắc thay thế
• Máy Turing
• Ngôn ngữ của Turing Machine
• Cấu trúc dữ liệu Turing Machine
• Đoán nhận ngôn ngữ
• Các biến thể của máy Turing
• Máy Turing tùy chọn tại chỗ
• Máy Turing bán vô hạn
• Máy Turing đa băng
• Máy Turing không đơn định