Đồ Á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 - Δ : là tập các kí tự không kết thúc (biến) - S ∈ N là kí tự xuất phát - P: là tập các luật sinh, mỗi luật sinh có dạng : A ->α A∈ Δ và α∈ (Δ ∪ Σ) * 3. Ngôn ngữ phi ngữ cảnh Định nghĩa: ngôn ngữ L được gọi là ngôn ngữ phi ngữ cảnh nểu tồn tại một văn phạm phi ngữ cảnh G sao cho L= L( G). Như vậy : thì một ngôn ngữ chính quy cũng là ngôn ngữ phi ngữ cảnh, hay nói cách khác lớp các ngôn ngữ chính quy là tập con trong lớp các ngôn ngữ phi ngữ cảnh. II. DẪN XUẤT 1. Dẫn xuất trực tiếp và dẫn xuất gián tiếp Dẫn xuất trực tiếp :Nếu A →b là luật sinh trong văn phạm G và α, β là 2 chuỗi bất kỳ, thì khi áp dụng luật sinh A →b vào chuỗi αAβ ta sẽ thu được chuỗi αbβ αAβ → αbβ Dẫn xuất gián tiếp: Giả sử: a1→ a2, a2→ a3, ..., am-1→ am ta viết a1→ *am (chú ý rằng a→ *a với mọi chuỗi a) 2. Dẫn xuất trái nhất và dẫn xuất phải nhất Dẫn xuất trái nhất: Để giới hạn sự lựa chọn các luật sinh trong quá trình dẫn xuất, nếu mỗi bước biến bên trái nhất của dạng câu được thay thế thì ta gọi là dẫn xuất trái nhất. Dẫn xuất phải nhất: Tương tự như dẫn xuất trái nhất nếu mỗi bước biến bên phải nhất của dạng câu được thay thế thì ta gọi là dẫn xuất phải nhất. Ví dụ: Xét văn phạm phi ngữ cảnh G = < Σ, Δ, S, P >, trong đó P bao gồm các luật sinh có dạng: 3