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

Bài giảng Lý thuyết tính toán: Bài 5 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về ngôn ngữ không chính quy; khái niệm ngôn ngữ không chính quy; độ dài dẫn xuất; bổ đề bơm (Pumping Lemma); . 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 5 NGÔN NGỮ KHÔNG 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. Bổ đề Bơm 3. Tổng kết chương 1 1 Khái niệm Khái niệm Ngôn ngữ chính quy Ngôn ngữ được đoán nhận bởi một DFA nào đó Ngôn ngữ không chính quy là gì Ví dụ Xét các ngôn ngữ sau trên bộ chữ Σ 0 1 là chính quy hay không chính quy B 0n 1n n 0 C w w có số ký hiệu 0 bằng số ký hiệu 1 D w w có số lần xuất hiện xâu con 01 và 10 là bằng nhau 2 Khái niệm Ngôn ngữ chính quy Ngôn ngữ được đoán nhận bởi một DFA nào đó Ngôn ngữ không chính quy là gì Ví dụ Xét các ngôn ngữ sau trên bộ chữ Σ 0 1 B 0n 1n n 0 Không chính quy C w w có số ký hiệu 0 bằng số ký hiệu 1 Không chính quy D w w có số lần xuất hiện xâu con 01 và 10 là bằng nhau Chính quy Làm sao để chứng minh một ngôn ngữ là không chính quy 3 Chu trình Hãy tưởng tượng một FSM có thể tạo ra các chuỗi rất dài Ví dụ Một DFA có Q 5 Làm sao để tạo ra một chuỗi dài Đi theo chu trình Nếu không theo chu trình thì chuỗi dài nhất được sinh ra là bao nhiêu s 5 Tất cả các chuỗi 5 đều phải đi theo một chu trình nào đó - Nếu ta có thể đi theo một chu trình n lần thì chuỗi được sinh ra đó sẽ nằm trong ngôn ngữ mà FSM đó đoán nhận - Nếu ta bỏ qua chu trình đó thì chuỗi được sinh ra vẫn sẽ nằm trong ngôn ngữ mà FSM đó đoán nhận 4 Ví dụ Xét một FSM sau Tất cả các chuỗi s được sinh ra có dạng s xyi z đều thuộc ngôn ngữ A mà máy FSM đoán nhận 5 Độ dài dẫn xuất Nếu A là ngôn ngữ chính quy và s là một xâu đủ dài thuộc A s p thì s có thể được viết như sau s xyz p được gọi là độ dài dẫn xuất pumping length Tất cả các ngôn ngữ chính quy có một thuộc tính đặc biệt Nếu ngôn ngữ không có thuộc tính này Là ngôn ngữ không chính quy 6 Bổ đề Bơm Bổ đề Bơm Bổ đề Bơm Pumping Lemma Nếu A là một ngôn ngữ chính quy thì tồn tại một số p sao cho nếu s là một xâu bất kỳ thuộc A có độ dài ít nhất là p thì s có thể được chia ra làm 3 phần s xyz thỏa mãn các điều kiện sau 1. xyi z A i 0 2. y gt 0 3. xy p 7 Bổ đề Bơm Sử dụng bổ

• Toán học
• Bài giảng Lý thuyết tính toán
• Lý thuyết tính toán
• Ngôn ngữ không chính quy
• Độ dài dẫn xuất
• Bổ đề Bơm (Pumping Lemma)
• Ngôn ngữ chính quy
• 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
• Ôtômat hữu hạn
• 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
• 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
• Nhận biết ngôn ngữ không chính quy
• Thiết kế ôtômat hữu hạn
• Toán tử chính quy
• Ôtômat hữu hạn không đơn định
• Toán tử chính quy với NFA
• Nondeterministic Finite State Automaton (NFA)
• Ngôn ngữ của biểu thức chính quy
• 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
• 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