tailieunhanh - Bài giảng Lí thuyết Ngôn ngữ hình thức và ôtômat: Chương 3- Nguyễn Thị Minh Huyền

Bài giảng "Lí thuyết Ngôn ngữ hình thức và ôtômat - Chương 3: Ngôn ngữ phi ngữ cảnh" cung cấp cho người đọc các kiến thức về: Ngôn ngữ ε - tự do, văn phạm dạng chuẩn Chomsky, cây dẫn xuất, điều kiện cần của ngôn ngữ phi ngữ cảnh, . | Lí thuyết Ngôn ngữ hình thức và Ôtômat Giảng viên Nguyễn Thị Minh Huyền Khoa Toán Cơ Tin học Trường ĐH Khoa học Tự nhiên Hà Nội Chương 3 Ngôn ngữ phi ngữ cảnh Ngôn ngữ phi ngữ cảnh Ngôn ngữ ε - tự do Văn phạm dạng chuẩn Chomsky Cây dẫn xuất Điều kiện cần của ngôn ngữ phi ngữ cảnh Tính đóng của ngôn ngữ phi ngữ cảnh Ôtômat đẩy xuống 2 Văn phạm ngôn ngữ ε - tự do Định nghĩa ε quy tắc quy tắc rỗng quy tắc có vế phải là từ rỗng Văn phạm ε tự do Văn phạm phi ngữ cảnh không chứa quy tắc rỗng Ngôn ngữ ε tự do L tồn tại văn phạm ε tự do sinh ra L Tính chất Mọi văn phạm phi ngữ cảnh G V P đều đưa được về văn phạm phi ngữ cảnh G V P tương đương với nó sao cho nếu G chứa quy tắc rỗng thì vế trái của nó phải là tiên đề ε . Với mọi ngôn ngữ phi ngữ cảnh L ngôn ngữ L ε luôn là ngôn ngữ ε tự do. VD S SB c A aA B B b 3 Văn phạm dạng chuẩn Chomsky Định nghĩa Văn phạm G V P được gọi là thuộc dạng chuẩn Chomsky nếu mỗi quy tắc của nó có 1 trong 2 dạng sau A BC A a với A B C V a Mọi văn phạm phi ngữ cảnh ε tự do đều đưa được về dạng chuẩn Chomsky tương đương với nó Thuật toán Loại bỏ quy tắc dạng A B Thay thế tất cả các kí hiệu cơ bản xuất hiện ở vế phải với độ dài gt 1 bằng một kí hiệu phụ mới Rút ngắn độ dài vế phải xuống không vượt quá 2 Ví dụ S bA aB A a aS bAA B B b bS aBB 4 Cây dẫn xuất 1 Khái niệm Với mỗi văn phạm phi ngữ cảnh G V P mỗi quy tắc đều có vế trái là một kí hiệu phụ Mỗi dẫn xuất w w0 w1 wn với w0 A V có thể biểu diễn dưới dạng cây gọi là cây dẫn xuất Chiều cao của cây T Số cung trên đường đi dài nhất xuất phát từ đỉnh gốc đến đỉnh ra lá kí hiệu h T Cây dẫn xuất kết Cây tương ứng với dẫn xuất w0 w1 wn trong đó wn chỉ chứa các kí hiệu cơ bản Cây dẫn xuất đầy đủ Cây dẫn xuất kết w0 w1 wn với w0 5 Cây dẫn xuất 2 Tính chất Trong cây dẫn xuất kết trong văn phạm dạng chuẩn Chomsky các đỉnh không kề với đỉnh ra bao giờ cũng có 2 cung đi ra các đỉnh kề với đỉnh ra bao giờ cũng có đúng 1 cung đi ra Nếu T là cây dẫn xuất trong văn phạm G mà vế phải các quy tắc đều có độ dài m

• Cơ khí - Chế tạo máy
• Lí thuyết Ngôn ngữ hình thức
• Bài giảng Lí thuyết Ngôn ngữ hình thức
• 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
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Ngôn ngữ chính quy
• Ôtômát hữu hạn
• Lớp ngôn ngữ chính quy
• kiến thức vật lý căn bản
• vật lí hạt nhân
• công suất điện
• cơ ứng dụng
• lý thuyết ôtômát
• kỹ thuật điện tử
• lý thuyết tính toán
• Phân tích diễn ngôn đa thức
• Nghĩa kinh nghiệm
• Quan hệ hình ảnh – văn bản
• Lý thuyết Ngôn ngữ học
• Ngôn ngữ học chức năng hệ thống
• công nghệ điện tử
• vi mạch điện tử
• mạch điện ứng dụng
• đề cương vi xử lí
• tài liệu học đại học
• tài liệu ôn thi vật lý
• Âm tiết và loại hình ngôn ngữ
• Tư cách ngôn ngữ học
• Lí thuyết âm tiết
• Âm vận học cổ điển Trung Hoa
• Âm tiết cảm thức
• Âm tiết ngữ âm học
• Phân tích âm vị học
• Hiện tượng đa thanh
• Lập luận nghịch hướng
• Lí thuyết đa thanh
• Hình thức đa thanh
• Quan hệ nghịch hướng
• Ngôn ngữ học