Chuyên đề: Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống

LỜI CẢM ƠN Trước hết, em xin chân thành cảm ơn các thầy cô giáo trong khoa Công nghệ thông tin Trường ĐH Kỹ thuật – Hậu cần CAND đã trang bị những kiến thức cơ bản, cần thiết và quý báu để em thực hiện chuyên đề của mình. Đặc biệt, em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy Nghiêm Văn Hưng, giáo viên giảng dạy, và thầy Cao Xuân Trường, người đã tận tình hướng dẫn, chỉ bảo và tạo mọi điều kiện thuận lợi giúp em trong quá trình thực hiện chuyên đề. Mặc dù đã rất cố gắng cùng nhận được sự giúp đỡ tận tâm của thầy giáo hướng dẫn, xong do trình độ còn hạn chế, tài liệu chưa được phong phú, và nội dung này khá khó đối với em nên không tránh khỏi những thiếu sót trong quá trình tiếp nhận kiến thức. Em rất mong nhận được sự quan tâm giúp đỡ, chỉ dẫn của thầy cô và sự góp ý từ bạn bè để trong thời gian tới em có thể tiếp tục tìm hiểu và xây dựng chuyên đề một cách hoàn thiện nhất. Em xin chân thành cảm ơn! GIỚI THIỆU TỔNG QUAN VỀ CHUYÊN ĐỀ Tên chuyên đề: Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống Sinh viên thực hiện: Hoàng Văn Thao Lớp: B3­D2B Giáo viên hướng dẫn: Thiếu úy Cao Xuân Trường Tính cấp thiết của chuyên đề: Lý thuyết ngôn ngữ hình thức và Automata đóng một vai trò rất quan trọng trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong việc xây dựng các ngôn ngữ lập trình, lý thuyết về các chương trình dịch. Các ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán cả cho dạng thông tin vào ­ ra lẫn kiểu thao tác. Lý thuyết ngôn ngữ hình thức, chính vì thực chất của nó là một lĩnh vực khoa học liên ngành; nhu cầu mô tả hình thức văn phạm được phát sinh trong nhiều ngành khoa học khác nhau từ ngôn ngữ học đến sinh vật học. Do đó những khía cạnh thích hợp của lý thuyết ngôn ngữ hình thức sẽ có tầm quan trọng quyết định trong các giáo trình về Lý thuyết ngôn ngữ hình thức và Automata. Lĩnh vực mà lý thuyết ngôn ngữ hình thức nghiên cứu là những mẫu hình (pattern) có cấu trúc bên trong ngôn ngữ hình thức, và đó là những khía cạnh hoàn toàn mang tính chất có cú pháp. Ngôn ngữ hình thức không còn đơn giản chỉ là để định nghĩa ngôn ngữ tự nhiên, mà nó vượt ra ngoài khỏi phạm vi đó và nó cũng là một cách để thể hiện được những quy tắc có cú pháp của ngôn ngữ tự nhiên. Mục tiêu của chuyên đề: Nghiên cứu tổng quan về văn phạm hình thức và các Automata, là những công cụ sinh ngôn ngữ, đồng thời đề cập đến các tính chất của ngôn ngữ chính quy, ngôn ngữ phi ngữ cảnh. Ngoài ra, cũng giới thiệu sơ lược về Trình biên dịch, một phần quan trọng của học phần Chương trình dịch gắn bó chặt chẽ với Lý thuyết ngôn ngữ hình thức và Automata, trong đó Văn phạm phi ngữ cảnh là cơ sở lý thuyết để xây dựng Bộ phân tích cú pháp, là thành phần quan trọng nhất trong một Trình biên dịch. Đối tượng nghiên cứu: Ngôn ngữ hình thức và lý thuyết Automata. Phạm vi nghiên cứu:  Ngôn ngữ phi ngữ cảnh cùng hai phương tiện để xác định chúng là Văn phạm phi ngữ cảnh;  Automata đẩy xuống. Phương pháp nghiên cứu:  Phương pháp nghiên cứu tài liệu;  Phương pháp chuyên gia;  Phương pháp thực nghiệm. Nội dung nghiên cứu:  Lý thuyết về Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống;  Các tính chất của Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống;  Ứng dụng của Ngôn ngữ hình thức và Automata với trình biên dịch. Chuyên đề gồm 5 chương: Chương I: Nhập môn về văn phạm và ngôn ngữ hình thức 1.1 Khái niệm ngôn ngữ 1.2 Văn phạm và ngôn ngữ sinh bởi văn phạm 1.3 Một số tính chất của ngôn ngữ Chương II: Văn phạm phi ngữ cảnh 2.1 Suy dẫn phi ngữ cảnh 2.2 Biến đổi các Văn phạm phi ngữ cảnh Chương III: Automata đẩy xuống 3.1 Automata đẩy xuống không tiền định 3.2 Automata đẩy xuống và Văn phạm phi ngữ cảnh Chương IV: Tổng quan về trình biên dịch 4.1 Ngôn ngữ lập trình 4.2 Trình biên dịch 4.3 Ứng dụng của Văn phạm phi ngữ cảnh và Automata đẩy xuống với trình biên dịch Chương V: Demo một bài toán 5.1 Bài toán và cơ sở lý thuyết 5.2 Demo ví dụ về sự tương đương giữa BTCQ và NFA Sản phẩm:  Báo cáo chuyên đề;  Chương trình demo cơ bản. MỤC LỤC ... - tailieumienphi.vn