Đồ Án Automat: cho biết dẫn xuất và hiển thị cây dẫn xuất Phụ Lục Đặt vấn đề Ngôn ngữ hình thức (Formal Languages) là môn học cơ sở của ngành công nghệ thông tin. Nó cho phép nghiên cứu, xây dựng mô hình toán học cho các máy tính toán. Đặc biệt trong xây dựng mô hình toán cho ngôn ngữ tự nhiên...Kiến thức về ngôn ngữ hình thức và automat là nền tảng cho nhiều lĩnh vực của khoa học máy tính và CNTT. Trong nghiên cứu về ngôn ngữ hình thức tập trung vào nghiên cứu các loại văn phạm. Đó là một tập hợp các quy tắc về cấu tạo từ và quy tắc về cách thức liên kết lại câu.Bằng cách áp đặt một số hạn chế trên các luật sinh Chomsky đề nghị một hệ thống phân loại văn phạm dựa vào cấu trúc của các luật sinh. Bao gồm 4 loại văn phạm là: văn phạm loại 0, văn phạm loại 1, văn phạm loại 2 và văn phạm loại 3. Văn phạm phi ngữ cảnh(văn phạm loại 2): là một loại văn phạm khá quan trọng . Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân tích cú pháp, vận dụng trong chương trình dịch và cho nhiều ứng dụng khác về xử lý chuỗi. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình mà biểu thức chính quy không thể đặc tả. Trong văn phạm 1 Đồ Án Automat: cho biết dẫn xuất và hiển thị cây dẫn xuất phi ngữ cảnh có rất nhiều khâu để xử lý, phân tích. Trong phạm vi của đồ án, chúng em xin trình bày những cơ sở lý thuyết về văn phạm phi ngữ cảnh(CFG) đồng thời lập trình đưa ra dẫn xuất và cây dẫn xuất của văn phạm đã cho.Do lượng kiến thức còn hạn chế nên trong quá trình thực hiện đồ án còn nhiều thiếu sót mong các thầy đóng góp ý kiến để chúng em hoàn thiện đồ án. PHẦN MỘT : CƠ SỞ LÝ THUYẾT I. VĂN PHẠM PHI NGỮ CẢNH VÀ NGÔN NGỮ PHI NGỮ CẢNH 1.Khái niệm văn phạm. Văn phạm G là một bộ gồm 4 thành phần G = < Σ, Δ, S, P >, trong đó: - Σ : bảng chữ cái, gọi là bảng chữ cái cơ bản (bảng chữ cái kết thúc – terminal symbol); - Δ , Δ ∩ Σ =Ø, gọi là bảng ký hiệu phụ (bảng chữ cái không kết thúc – nonterminal symbol); - S ∈ Δ - ký hiệu xuất phát hay tiên đề (start variable); - P : tập các luật sinh (production rules) dạng α→β, α, β ∈ (Σ ∪ Δ)*, trong α chứa ít nhất một ký hiệu không kết thúc (đôi khi, ta gọi chúng là các qui tắc hoặc luật viết lại). 2.Khái niệm văn phạm phi ngữ cảnh Định nghĩa: Một văn phạm phi ngữ cảnh được định nghĩa : G = < Σ, Δ, S, P > Trong đó: 2 Đồ Án Automat: cho biết dẫn xuất và hiển thị cây dẫn xuất - Σ : là bảng chữ cái - ...