TAILIEUCHUNG - Lý thuyết ngôn ngữ hình thức và ôtômát - Chương 3

ÔTÔMAT ĐẨY XUỐNG VÀ NGÔN NGỮ PHI NGỮ CẢNH Đối với các lớp văn phạm được phân loại theo Chomsky, lớp văn phạm phi ngữ cảnh có vai trò quan trọng nhất trong việc ứng dụng để xây dựng các ngôn ngữ lập trình và chương trình dịch. Trong quá trình dịch từ chương trình nguồn ra chương trình đích, người ta sử dụng cấu trúc cú pháp của văn phạm phi ngữ cảnh để phân tích các xâu vào. Cấu trúc cú pháp của một xâu vào được xác định từ dãy các quy tắc suy từ xâu đó | CHƯƠNG III ÔTÔMAT ĐẨY XUỐNG VÀ NGÔN NGỮ PHI NGỮ CẢNH Đối với các lớp văn phạm được phân loại theo Chomsky lớp văn phạm phi ngữ cảnh có vai trò quan trọng nhất trong việc ứng dụng để xây dựng các ngôn ngữ lập trình và chương trình dịch. Trong quá trình dịch từ chương trình nguồn ra chương trình đích người ta sử dụng cấu trúc cú pháp của văn phạm phi ngữ cảnh để phân tích các xâu vào. Cấu trúc cú pháp của một xâu vào được xác định từ dãy các quy tắc suy từ xâu đó. Dựa vào dãy các quy tắc đó bộ phân tích cú pháp của chương trình dịch sẽ cho biết xâu vào đang xét có thuộc vào xâu do văn phạm phi ngữ cảnh sinh ra hay không. Nói cách khác là với xâu vào 0 và một văn phạm phi ngữ cảnh G hỏi xem 0eL G hay không Nếu có thì hãy tìm cách biểu diễn 0 bằng văn phạm tức là tìm các quy tắc sinh của văn phạm G để sinh ra xâu 0. . VĂN PHẠM PHI NGỮ CẢNH VÀ CÂY SUY DẪN CỦA NÓ. . Định nghĩa Cho văn phạm phi ngữ cảnh G A a S P . Cây suy dẫn trong văn phạm G là một cây có gốc thoả mãn bốn yêu cầu sau 1. Ở mỗi đỉnh được gán một nhãn. Nhãn gán ở đỉnh là các ký hiệu trong tập XoA. Gốc của cây được gán nhãn là S. 2. Mỗi đỉnh trong được gán nhãn là một ký hiệu nào đó trong A. 3. Mỗi đỉnh ngoài lá của cây được gán nhãn là một ký hiệu trong tập s. 4. Nếu đỉnh m được gán nhãn là AeA còn các đỉnh n1 n2 . nk là các con của đỉnh m theo thứ tự từ trái sang phải và được gán nhãn B1 B2 . Bk tương ứng thì A B1B2. Bk là một quy tắc trong P của văn phạm G. Nếu đọc tất cả nhãn ở các lá theo thứ tự từ trái sang phải ta sẽ nhận được một từ nào đó. Từ đó sẽ là một phần tử trong L G và được gọi là kết quả của cây suy dẫn trong G. Thí dụ 1 Cho các văn phạm phi ngữ cảnh Gi a b c S A S S S S A A a b c A S S a b c G2 a b S A S S Sa Aa A aAb ab G2 S ai a2 . an S S S aSa S aa asS G4 if then else for do a b c S A S S if b then A if b then A else S S a A for c do S a . Cây suy dẫn của từ b a c b trong G1 là 43 S S b S J a 0 b c a J Cây suy dẫn của từ anbnam trong G2 là n lần Cây suy dẫn của từ a1a2. anan. .

• Kỹ thuật lập trình
• ngôn ngữ hình thức
• Lý thuyết ôtômát
• máy turing
• trình biên dịch
• ô tô mát hữu hạn
• Giáo trình Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức và ô tô mát
• Lý thuyết ngôn ngữ hình thức
• Ngôn ngữ hình thức và ô tô mát
• Khái niệm otô mát
• Ngôn ngữ phi ngữ cả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
• Lý thuyết ngôn ngữ
• Ngôn ngữ lập trình
• Văn phạm hình thức
• Kỹ thuật lập trình
• Đề thi học kỳ
• Đề thi Lý thuyết ngôn ngữ hình thức
• Bài tập Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức và ôtômat
• Lý thuyết ngôn ngữ hình thức và atomat
• 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
• 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
• 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
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ hình thức và ôtômát
• Phép toán trên từ
• Phép toán trên ngôn ngữ
• Dạng chuẩn Chomsky
• Văn phạm phi ngữ cảnh
• Otomat đẩy xuống
• Chương trình dịch
• Ngôn ngữ học
• vai trò của ngôn ngữ
• ngôn ngữ và sự chắc chắn
• ngôn ngữ và nhận thức
• tri thức và ngôn ngữ
• tìm hiểu ngôn ngữ học
• 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
• Văn phạm chính quy
• Bài toán bao hàm ngôn ngữ
• Giáo trình Ôtômát và ngôn ngữ hình thức
• Ngôn ngữ sinh
• Văn phạm tương đương
• Phân loại ngôn ngữ
• Phương pháp biểu diễn ôtômát
• Ôtômát đẩy xuống
• Suy dẫn phi ngữ cảnh
• Cây suy dẫn
• Tìm về cội nguồn ngôn ngữ
• Cội nguồn ngôn ngữ
• Hình thức gốc của ý thức
• Động tác chỉ dẫn
• Cội nguồn ý thức
• Ngôn ngữ Ý thức
• Ngôn ngữ hỗn hợp