TAILIEUCHUNG - Bài giảng Ngôn ngữ hình thức: Chương 3 - Nguyễn Thị Hồng

Bài giảng Ngôn ngữ hình thức: Chương 3 Văn phạm phi ngữ cảnh, cung cấp cho người học những kiến thức như: Suy dẫn phi ngữ cảnh; Cây suy dẫn và sự nhập nhằng; Giản lược văn phạm phi ngữ cảnh; Dạng chuẩn Chomsky. Mời các bạn cùng tham khảo! | Chương 3 Văn phạm phi ngữ cảnh 1 Nội dung Suy dẫn phi ngữ cảnh Cây suy dẫn và sự nhập nhằng Giản lược văn phạm phi ngữ cảnh Dạng chuẩn Chomsky 2 Suy dẫn phi ngữ cảnh Văn phạm phi ngữ cảnh là văn phạm trong đó các sản xuất có dạng A với A Suy dẫn phi ngữ cảnh tại mỗi bước chỉ áp dụng sản xuất phi ngữ cảnh 3 Một số ví dụ về suy dẫn phi ngữ cảnh Ví dụ 1 Trong ngôn ngữ lập trình A B C Z 0 1 2 3 4 5 6 7 8 9 Kí hiệu không kết thúc Kí hiệu kết thúc A B C Z 0 1 2 9 4 Một số ví dụ về suy dẫn phi ngữ cảnh Ví dụ 2 Trong văn phạm tiếng Việt có các quy tắc bò mèo tôi nó ăn nằm Kí hiệu không kết thúc Kí hiệu kết thúc bò mèo tôi nó ăn nằm là các từ tiếng Việt 5 Suy dẫn phi ngữ cảnh Định lý định lý phân dã suy dẫn Cho G P S là văn phạm phi ngữ cảnh đặt V . Nếu trong G có suy dẫn u1u2 un gt kG v trong đó ui v V thì tồn tại vi V và ki N i 1 2 n sao cho ui gt ki vi Với mọi i 1 2 n v v1v2 vn k1 k2 kn k Chứng minh lý thuyết ngôn ngữ và tính toán Nguyễn Văn6 Cây suy dẫn và sự nhập nhằng Định nghĩa cây suy dẫn Trong văn phạm phi ngữ cảnh G P S Cây suy dẫn là cây mà mỗi đỉnh được gắn một nhãn là một phần tử thuộc tập và thỏa các điều kiện i. Nhãn của gốc là kí hiệu đầu S. ii. Nhãn của mỗi đỉnh trong là kí hiệu không kết thúc. Nhãn của mỗi lá là kí hiệu kết thúc hoặc . iii. Với mỗi đỉnh trong có nhãn A và các con có nhãn là X1 X2 Xk thì A X1X2Xk là một sản xuất trong G. iv. Nếu một lá có nhãn là thì lá đó là con duy nhất của cha nó 7 Cây suy dẫn tiếp Cây con là một cây tạo thành bởi một đỉnh và mọi hậu duệ của nó cùng với các nhãn và cung liên kết chúng. Gốc cây con có nhãn là A ta gọi cây con đó là A-cây Biên kết quả của một cây suy dẫn hay của một A-cây là xâu tạo thành bằng cách ghép tiếp các lá của cây theo trật tự từ trái qua phải ta được một câu gọi là kết quả. 8 Ví dụ về cây suy dẫn Ví dụ xét văn phạm G S A a b P S với P gồm S aAS a A SbA SS ba Một dẫn xuất của G S gt aAS gt aSbAS gt aabAS gt aabbaS gt aabbaa S 1 a A S 2 3 4 S A a 5 b 6 7 8 a a b 10 11 9 9 Cây suy dẫn tiếp .

• Kỹ thuật lập trình
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ hình thức
• Văn phạm phi ngữ cảnh
• Suy dẫn phi ngữ cảnh
• Cây suy dẫn
• Ngôn ngữ lập trình
• Lí thuyết Ngôn ngữ hình thức
• Bài giảng Lí thuyết Ngôn ngữ hình thức
• Lí thuyết Ngôn ngữ hình thức và ôtômat
• Ngôn ngữ phi ngữ cảnh
• Bài giảng Ngôn ngữ hình Đại cương về ngôn ngữ
• Biểu diễn ngôn ngữ
• Hệ viết lại
• Phép toán trên tập hợp
• Bài giảng Trị liệu ngôn ngữ
• Trị liệu ngôn ngữ
• Đánh giá ngôn ngữ
• Các dạng ngôn ngữ
• Các hình thức ngôn ngữ
• Trẻ bị rối loạn ngôn ngữ
• Âm vị học ngữ pháp
• Ngôn ngữ hình thức và ôtômát
• Văn phạm hình thức
• Phép toán trên từ
• Phép toán trên ngôn ngữ
• Ngôn ngữ chính quy
• Máy Turing
• Dạng chuẩn Chomsky
• Otomat đẩy xuống
• Chương trình dịch
• Ôtômát hữu hạn
• Văn phạm chính quy
• Bài toán bao hàm ngôn ngữ
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Lớp ngôn ngữ chính quy
• Automat hữu hạn
• Bài giảng Ôtômát và ngôn ngữ hình thức
• Phân cấp văn phạm
• Cấu tạo Ôtômát
• Xây dựng văn phạm cho ngôn ngữ
• Phép toán trên xâu
• Ngôn ngữ lập trình Pascal
• Ôtômát đẩy xuống
• Ôtômat đẩy xuống
• Bài toán xâu rỗng
• Thuật toán Thampson
• Ngôn ngữ đoán nhận
• Bản chất của thuật toán
• Otomat hữu hạn
• Bài giảng công nghệ thông tin
• Tập bài giảng Ngôn ngữ hình thức
• Automat hữu hạn đơn định
• Automat đẩy xuống
• Lý thuyết Automat
• Lý thuyết tính toán Otomat
• Lý thuyết ngôn ngữ hình thức
• Kỹ thuật mô phỏng
• Kỹ thuật chứng minh
• Otomat và ngôn ngữ hình thức
• Văn phạm và ngôn ngữ hình thức
• Bài giảng Đặc tả hình thức
• Đặc tả hình thức
• Mô hình Thế giới thực
• Ngôn ngữ đặc tả hình thức
• Quy trình công nghệ phần mềm
• Các tính chất của quan hệ
• Phép toán trên các tập hợp
• Các quan hệ tương đương
• Chương trình con
• Thiết kế thuật toán
• Ôtômát tuyến tính giới nội
• Máy turing tiền định
• Cấu tạo máy Turing
• Ngôn ngữ hình thức và Ôtômat
• Ôtomat hữu hạn