Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Sư phạm Luận văn văn phạm phi ngữ cảnh và ứng dụng trong phân tích cú pháp...

Tài liệu Luận văn văn phạm phi ngữ cảnh và ứng dụng trong phân tích cú pháp

.PDF
55
112
145

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ĐẶNG VĂN QUÂN VĂN PHẠM PHI NGỮ CẢNH VÀ ỨNG DỤNG TRONG PHÂN TÍCH CÚ PHÁP LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ĐẶNG VĂN QUÂN VĂN PHẠM PHI NGỮ CẢNH VÀ ỨNG DỤNG TRONG PHÂN TÍCH CÚ PHÁP Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. KIỀU VĂN HƯNG Hà Nội - 2018 LỜI CẢM ƠN Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi đã hoàn thành luận văn tốt nghiệp thạc sĩ của mình. Để có được kết quả này, tôi xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành nhất đến thầy giáo, TS. Kiều Văn Hưng, người đã định hướng nghiên cứu và truyền thụ kiến thức cho tôi trong suốt thời gian thực hiện luận văn của mình. Tôi xin chân thành cảm ơn sự giúp đỡ quý báu của các thầy cô giáo trong bộ môn Toán Ứng dụng nói riêng và khoa Toán, trường Đại học Sư phạm Hà Nội 2 nói chung. Xin cảm ơn những người thân trong gia đình và tất cả những người bạn thân yêu đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và thực hiện luận văn của mình. Tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô và các bạn để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn!. Hà Nội, ngày 08 tháng 06 năm 2018 Tác giả luận văn Đặng Văn Quân 1 LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi, được thực hiện dưới sự hướng dẫn của thầy giáo TS. Kiều Văn Hưng. Trong quá trình nghiên cứu, tôi đã kế thừa thành quả khoa học của các nhà khoa học với sự trân trọng và biết ơn. Các kết quả trích dẫn trong luận văn này đã được chỉ rõ nguồn gốc. Hà Nội, ngày 08 tháng 06 năm 2018 Tác giả luận văn Đặng Văn Quân 2 Mục lục MỞ ĐẦU 5 1 7 Kiến thức chuẩn bị 1.1. Ngôn ngữ và biểu diễn ngôn ngữ . . . . . . . . . . . . . 8 1.1.1. Ngôn ngữ . . . . . . . . . . . . . . . . . . . . . . 8 1.1.2. Biểu diễn ngôn ngữ . . . . . . . . . . . . . . . . 14 Văn phạm . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3. Ngôn ngữ phi ngữ cảnh . . . . . . . . . . . . . . . . . . . 18 1.2. 2 Văn phạm phi ngữ cảnh 20 2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2. Cây dẫn xuất trong văn phạm phi ngữ cảnh . . . . . . . 25 2.3. Các chiến lược phân tích cú pháp . . . . . . . . . . . . . 29 3 Ứng dụng của văn phạm phi ngữ cảnh 35 3.1. Tổng quan về ứng dụng của văn phạm phi ngữ cảnh . . 36 3.2. Một số thuật toán phân tích cú pháp . . . . . . . . . . . 43 3 3.2.1. Thuật toán Left to right parse - Leftmost derivation (LL) . . . . . . . . . . . . . . . . . . . . . . 43 3.2.2. Thuật toán Earley . . . . . . . . . . . . . . . . 47 3.2.3. Thuật toán Cocke-Younger-Kasami (CYK) . . . 49 Kết luận 52 Tài liệu tham khảo 52 4 Mở đầu 1. Lý do chọn đề tài Văn phạm phi ngữ cảnh là một là mô hình toán học sản sinh ra lớp ngôn ngữ phi ngữ cảnh.Văn phạm phi ngữ cảnh cho phép mô tả các biểu thức số học trong các dấu ngoặc lồng nhau hay những cấu trúc khối trong ngôn ngữ lập trình, có nhiều ứng dụng thực tế rất quan trọng, đặc biệt là trong phân tích cú pháp. Ngôn ngữ hình thức được nhà ngôn ngữ học nổi tiếng Noam Chomsky phân ra làm bốn loại: ngôn ngữ ngữ cấu (nhóm 0), ngôn ngữ cảm ngữ cảnh (nhóm 1), ngôn ngữ phi ngữ cảnh (nhóm 2) và ngôn ngữ chính quy (nhóm 3). Với mong muốn tìm hiểu sâu hơn về lớp ngôn ngữ phi ngữ cảnh và văn phạm phi ngữ cảnh em đã quyết định chọn đề tài nghiên cứu cho luận văn tốt nghiệp thạc sĩ chuyên ngành Toán ứng dụng là “Văn phạm phi ngữ cảnh và ứng dụng trong phân tích cú pháp”. 2. Mục đích nghiên cứu Tìm hiểu về văn phạm và ngôn ngữ phi ngữ cảnh trong lý thuyết ngôn ngữ hình thức. 5 3. Nhiệm vụ nghiên cứu Trình bày một cách hệ thống về văn phạm, ngôn ngữ phi ngữ cảnh và ứng dụng liên quan. 4. Đối tượng và phạm vi nghiên nghiên cứu • Đối tượng nghiên cứu: Văn phạm và ngôn ngữ phi ngữ cảnh. • Phạm vi nghiên cứu: Nghiên cứu tổng quan về văn phạm và ngôn ngữ phi ngữ cảnh. 5. Phương pháp nghiên cứu Tìm hiểu các tài liệu, sách, báo liên quan đến các kết quả đã có về văn phạm và ngôn ngữ phi ngữ cảnh. Tổng hợp kiến thức và trình bày một cách hệ thống. 6. Đóng góp mới Hệ thống các kiến thức về văn phạm phi ngữ cảnh và ứng dụng của chúng, góp phần làm phong phú hơn các kết quả, sự hiểu biết về văn phạm và ngôn ngữ phi ngữ cảnh. Hi vọng luận văn là một tài liệu tham khảo hữu ích về lý thuyết và ngôn ngữ hình thức. 6 Chương 1 Kiến thức chuẩn bị Có thể hình dung một văn phạm như một “thiết bị tự động” có khả năng sinh ra một tập hợp các từ trên một bảng chữ cho trước. Mỗi từ được sinh ra sau một số hữu hạn bước thực hiện các quy tắc của văn phạm. Việc xác định một ngôn ngữ trên bảng chữ cho trước có thể được thực hiện bằng một trong các cách thức sau: Cách 1: Đối với mỗi từ thuộc ngôn ngữ đã cho, ta có thể chọn một quy cách hoạt động của “thiết bị tự động” để sau một số hữu hạn bước làm việc nó dừng và sinh ra chính từ đó. Cách 2: “Thiết bị tự động” có khả năng lần lượt sinh ra tất cả các từ trong ngôn ngữ đã cho. Cách 3: Với mỗi từ cho trước, “thiết bị tự động” có thể cho biết từ đó có thuộc ngôn ngữ đã cho hay không. Trong lý thuyết văn phạm, người ta đã chứng minh được rằng ba cách thức trên là tương đương nhau hay văn phạm làm việc theo các cách trên là tương đương nhau. Vì vậy, ở đây ta quan tâm đến cách thứ 7 nhất, tức là ta xét văn phạm như là một “thiết bị tự động” sinh ra các từ. Vì lẽ đó mà người ta còn gọi các “thiết bị tự động” đó là văn phạm sinh. Việc sinh ra các từ có thể được thực hiện bằng nhiều cách khác nhau. Các từ có thể được sinh ra bởi các văn phạm, bởi các Otomat, bởi các máy hình thức như máy Turing, . . . Ở đây ta đề cập đến cách của N.Chomsky đưa ra vào những năm 1956-1957. 1.1. Ngôn ngữ và biểu diễn ngôn ngữ 1.1.1. Ngôn ngữ Tập Σ khác rỗng gồm hữu hạn hay vô hạn các ký hiệu được gọi là bảng chữ. Mỗi phần tử a ∈ Σ được gọi là một chữ hay một ký hiệu. Ở đây ta chỉ xét bảng chữ có hữu hạn phần tử. Ví dụ 1.1. Dưới đây là các bảng chữ: + Σ = {a, b, c, ..., x, y, z}. + ∆ = {α, β, γ, δ, ε, η, ϕ, κ, µ, χ, ν, π, θ, ρ, σ, τ, ω, ξ, ψ}, + Γ = {0, 1}, + W = {if, then, else, a, b, c, d, e, f, +, −, ∗, /, =, 6=} . Giả sử có bảng chữ Σ = {a1 , a2 , . . . , am }, một dãy các chữ α = ai1 ai2 . . . ait , với aij ∈ Σ (1 ≤ j ≤ t) được gọi là một từ hay một xâu trên bảng chữ Σ. Tổng số vị trí của các ký hiệu xuất hiện trong xâu α được gọi là độ dài của từ α và ký hiệu là |α|. Như vậy, một từ trên bảng chữ Σ là một xâu hữu hạn gồm một số 8 lớn hơn hay bằng không các chữ của Σ, trong đó một chữ có thể xuất hiện nhiều lần. Xâu không có chữ nào được gọi là từ rỗng và được ký hiệu là ε. Rõ ràng từ rỗng là từ thuộc mọi bảng chữ. Hai từ α = a1 a2 . . . an và β = b1 b2 . . . bm được gọi là bằng nhau, và được ký hiệu là α = β, nếu n = m và ai = bi với mọi i = 1, 2, . . . , n. Nếu α là một từ trên bảng chữ Σ, và Σ ⊆ ∆ thì α cũng là từ trên bảng chữ ∆. Tập mọi từ trên bảng chữ Σ được ký hiệu là Σ∗ , còn tập mọi từ khác rỗng trên bảng chữ Σ được ký hiệu là Σ+ . Như vậy Σ+ = Σ∗ \ {ε} và Σ∗ = Σ+ ∪ {ε}. Dễ thấy rằng các tập Σ∗ và Σ+ là vô hạn. Về cấu trúc đại số thì Σ∗ là một vị nhóm tự do sinh bởi Σ với đơn vị là từ rỗng ε, còn Σ+ là một nửa nhóm tự do sinh bởi Σ. Có thể chứng minh được rằng các tập Σ∗ và Σ+ là vô hạn đếm được. Ví dụ 1.2. + Ta có ε, 0, 01, 101, 1010, 110011 là các từ trên bảng chữ Γ = {0, 1}. + Các xâu ε, beautiful, happy, holiday là các từ trên bảng chữ Σ = {a, b, c, . . . , z}. Cho bảng chữ Σ, mỗi tập con L ⊆ Σ∗ được gọi là một ngôn ngữ hình thức (hay ngôn ngữ) trên bảng chữ Σ. Tập rỗng, ký hiệu ∅, là một ngôn ngữ không gồm một từ nào và được gọi là ngôn ngữ rỗng. Vậy ngôn ngữ rỗng là ngôn ngữ trên mọi bảng chữ. Chú ý rằng ngôn ngữ rỗng: ∅ là khác với ngôn ngữ chỉ gồm một từ rỗng: {ε}. 9 Ví dụ 1.3. + L = {ε, 0, 1, 01, 10, 00, 11, 011, 100} là một ngôn ngữ trên bảng chữ cái Γ = {0, 1}. + L = {a, b, c, aa, ab, ac, abc} là ngôn ngữ trên bảng chữ Σ = {a, b, c}. + L1 = {ε, a, b, abb, aab, aaa, bbb, abab}, L2 = {an bn |n ∈ N } là hai ngôn ngữ trên bảng chữ Σ = {a, b}, L1 là ngôn ngữ hữu hạn trong khi L2 là ngôn ngữ vô hạn. Mỗi từ thuộc ngôn ngữ L2 có số chữ a bằng số chữ b với a và b không xen kẽ, a nằm ở phía trái và b ở phía phải của từ. Một số phép toán cơ bản Các họ ngôn ngữ cụ thể thường được đặc trưng một cách tiện lợi qua các phép toán xác định trên ngôn ngữ, họ đó gồm các ngôn ngữ nhận được bằng việc tổ hợp từ một số ngôn ngữ cho trước bởi một số phép toán nào đó. Vì mỗi ngôn ngữ là một tập hợp nên ta có các phép toán đại số tập hợp như là phép giao, phép hợp, phép hiệu, phép lấy bù trên các ngôn ngữ. Chẳng hạn, với L1 và L2 là hai ngôn ngữ trên bảng chữ Σ thì ta cũng có các ngôn ngữ mới sau đây trên bảng chữ Σ : L1 ∪ L2 , L1 ∩ L2 , L1 .L2 , Σ∗ \ L1 . Dưới đây chúng ta sẽ trình bày các phép toán trên ngôn ngữ Hợp của hai ngôn ngữ L1 và L2 trên bảng chữ Σ, ký hiệu L1 ∪ L2 , là một ngôn ngữ trên bảng chữ Σ, đó là tập từ: L = {ω ∈ Σ∗ | ω ∈ L1 hoặc ω ∈ L2 }. Định nghĩa phép hợp có thể mở rộng cho một số hữu hạn các ngôn ngữ, tức là hợp của các ngôn ngữ L1 , L2 , . . . , Ln trên bảng chữ Σ, là tập từ: n [ Li = {ω ∈ Σ∗ | ω ∈ Li với i nào đó, 1 ≤ i ≤ n}. i=1 Nhận xét 10 Dễ dàng thấy rằng phép hợp các ngôn ngữ có các tính chất sau: i) Phép hợp hai ngôn ngữ có tính giao hoán: L1 ∪ L2 = L2 ∪ L1 . ii) Phép hợp các ngôn ngữ có tính kết hợp: (L1 ∪L2 )∪L3 = L1 ∪(L2 ∪L3 ). iii) Với mọi ngôn ngữ L trên Σ thì: L ∪ ∅ = ∅ ∪ L = L và L ∪ Σ∗ = Σ∗ . Giao của hai ngôn ngữ L1 và L2 trên bảng chữ cái Σ, ký hiệu L1 ∩ L2 , là một ngôn ngữ trên bảng chữ Σ, đó là tập từ: L = {ω ∈ Σ∗ | ω ∈ L1 và ω ∈ L2 }. Định nghĩa phép giao có thể mở rộng cho một số hữu hạn các ngôn ngữ, tức là giao của các ngôn ngữ L1 , L2 , . . . , Ln trên bảng chữ Σ, là tập từ: n \ Li = {ω ∈ Σ∗ | ω ∈ Li với mọi i, 1 ≤ i ≤ n}. i=1 Nhận xét Dễ dàng thấy ràng, phép giao các ngôn ngữ có tính chất sau: i) Phép giao hai ngôn ngữ có tính giao hoán: L1 ∩ L2 = L2 ∩ L1 . ii) Phép giao các ngôn ngữ có tính kết hợp: (L1 ∩L2 )∩L3 = L1 ∩(L2 ∩L3 ). iii) Phép giao các ngôn ngữ có tính phân phối đối với phép hợp: (L1 ∩ L2 ) ∪ L3 = (L1 ∪ L3 ) ∩ (L2 ∪ L3 ) (L1 ∪ L2 ) ∩ L3 = (L1 ∩ L3 ) ∪ (L2 ∩ L3 ). iv) Với mọi ngôn ngữ L trên Σ thì: L ∩ ∅ = ∅ ∩ L = L và L ∩ Σ∗ = Σ∗ . Ngôn ngữ phần bù của ngôn ngữ L trên bảng chữ Σ, ký hiệu CΣ L (hay đơn giản là CL, nếu không gây nhầm lẫn), là một ngôn ngữ trên bảng chữ cái Σ, đó là tập từ: CΣ L = {ω ∈ Σ∗ | ω ∈ / L}. Nhận xét 11 Dễ dàng thấy rằng phép lấy phần bù các ngôn ngữ có các tính chất sau: i) CΣ {ε} = Σ+ , CΣ Σ+ = {ε}. ii) CΣ ∅ = Σ∗ , CΣ Σ∗ = ∅. iii) C(CL1 ∪ CL2 ) = L1 ∩ L2 . Ví dụ 1.4. + Cho ngôn ngữ L1 = {ε, 0, 01}, L2 = {ε, 01, 10} trên bảng chữ Σ = {0, 1}, khi đó ta có: L1 ∪ L2 = {ε, 0, 01, 10}, L1 ∩ L2 = {ε, 01}. + Cho ngôn ngữ L = {ω ∈ Σ∗ , với |ω| là một số chẵn }, khi đó ta có: CΣ L = {ω ∈ Σ+ , với |ω| là một số lẻ }. Cho hai ngôn ngữ L1 trên bảng chữ Σ1 và L2 trên bảng chữ Σ2 . Nhân ghép hay tích của hai ngôn ngữ L1 và L2 là một ngôn ngữ trên bảng chữ Σ1 ∪ Σ2 , ký hiệu L1 L2 , đuợc xác định bởi: L1 L2 = {αβ | α ∈ L1 và β ∈ L2 }. Nhận xét Dễ dàng nhận thấy phép nhân ghép (tích) các ngôn ngữ có các tính chất sau: i) Phép nhân ghép có tính kết hợp: với mọi ngôn ngữ L1 , L2 và L3 , ta có: (L1 L2 )L3 = L1 (L2 L3 ) = L1 L2 L3 . ii) Phép nhân ghép có tính phân phối đối với phép hợp, nghĩa là L1 (L2 ∪ L3 ) = L1 L2 ∪ L1 L3 , (L2 ∪ L3 )L1 = L2 L1 ∪ L3 L1 . 12 iii) Đặc biệt: Phép nhân ghép không có tính phân phối đối với phép giao. Phép hợp, phép giao không có tính phân phối đối với phép nhân ghép. Tức là với mọi ngôn ngữ L1 , L2 và L3 , thì: L1 (L2 ∩ L3 ) 6= (L1 L2 ) ∩ (L1 L3 ) và L1 ∪ (L2 L3 ) 6= (L1 ∪ L2 )(L1 ∪ L3 ), L1 ∩ (L2 L3 ) 6= (L1 ∩ L2 )(L1 ∩ L3 ). Ví dụ 1.5. Đây là một phản ví dụ để chỉ ra rằng phép nhân ghép không có tính phân phối đối với phép giao. Phép hợp, phép giao không có tính phân phối đối với phép nhân ghép. Xét các ngôn ngữ L1 = {0, 01}, L2 = {01, 10}, L3 = {0} trên bảng chữ cái Σ = {0, 1}. + Có thể kiểm tra được rằng phép nhân ghép không có tính phân phối đối với phép giao: Ta có: L2 ∩ L3 = ∅, do đó: L1 (L2 ∩ L3 ) = ∅, Mặt khác, ta có L1 L2 = {001, 010, 0101, 0110} và L1 L3 = {00, 010}, do đó: (L1 L2 ) ∩ (L1 L3 ) = 010. Vậy L1 (L2 ∩ L3 ) 6= (L1 L2 ) ∩ (L1 L3 ), tức là phép nhân ghép không có tính phân phối đối với phép giao. + Kiểm tra tính phân phối của phép hợp, phép giao đối với phép nhân ghép: Ta có: L2 L3 = {010, 100}, do đó: L1 ∪ (L2 L3 ) = {0, 01, 010, 100}, Mặt khác ta cũng có L1 ∪ L2 = {0, 01, 10} và L1 ∪ L3 = {0, 01}, do đó: (L1 ∪ L2 )(L1 ∪ L3 ) = {00, 001, 010, 0101, 100, 1001}. Vậy L1 ∪ (L2 L3 ) 6= (L1 ∪ L2 (L1 ∪ L3 ), tức là phép hợp không có tính phân phối đối với phép nhân ghép. 13 Tương tự, đối với phép giao, ta có: L2 L3 = {010, } do đó: L1 ∩ (L2 L3 ) = ∅. Mặt khác L1 ∩ L2 = {01}, L1 ∩ L3 = {0}, do đó: (L1 ∩ L2 )(L1 ∩ L3 ) = {010}. Vậy L1 ∩ (L2 L3 ) 6= (L1 ∩ L2 )(L1 ∩ L3 ). Tức là phép giao không có tính phân phối đối với phép nhân ghép. 1.1.2. Biểu diễn ngôn ngữ Biểu diễn ngôn ngữ hữu hạn: Biểu diễn chúng bằng cách liệt kê tất cả các chuỗi thuộc vào chúng. Ví dụ 1.6. L1 = {ε}, L2 = {a, ba, aaba, bbbbb}. Ví dụ 1.7. Ngôn ngữ gồm các số tự nhiên nhỏ hơn 20 và lớn hơn 12, là L = {13, 14, 15, 16, 17, 18, 19}. Biểu diễn ngôn ngữ vô hạn: Không thể liệt kê tất cả các chuỗi thuộc ngôn ngữ được. Trong trường hợp đơn giản thì ngôn ngữ được biểu diễn thông qua một phát biểu hay một tân từ. Ví dụ 1.8. Ngôn ngữ gồm các số thực nhỏ hơn 5. L = {x | (x ∈ R) và (x < 5)}. Ví dụ 1.9. Ngôn ngữ gồm các số. L1 = {ai /i là một số nguyên tố}, L2 = {ai bi /i ≥ j ≥ 0}. 14 1.2. Văn phạm Định nghĩa 1.1. Văn phạm G là một bộ sắp thứ tự gồm 4 thành phần: G = hΣ, ∆, S, P i, trong đó: + Σ là một bảng chữ, gọi là bảng chữ cơ bản (hay bảng chữ kết thúc), mỗi phần tử của nó được gọi là một ký hiệu kết thúc hay ký hiệu cơ bản; + ∆ là một bảng chữ, ∆ ∩ Σ = ∅, gọi là bảng ký hiệu phụ (hay bảng chữ không kết thúc), mỗi phần tử của nó được gọi là một ký hiệu không kết thúc hay ký hiệu phụ. + S ∈ ∆ được gọi là ký hiệu xuất phát hay tiên đề; + P là tập hợp các quy tắc sinh có dạng α → β, α được gọi là vế trái và β được gọi là vế phải của quy tắc này, với α, β ∈ (Σ ∪ ∆)∗ và trong α chứa ít nhất một ký hiệu không kết thúc.  P = α → β | α = α0 Aα00 , với A ∈ ∆, α0 , α00 , β ∈ (Σ ∪ ∆) Chẳng hạn, với Σ = {0, 1}, ∆ = {S, A, B} thì các quy tắc S → 0S1A, 0AB → 1A1B, A → ε, . . . là các quy tắc hợp lệ vì vế trái luôn chứa ít nhất 1 ký hiệu phụ thuộc ∆. Nhưng các quy tắc dạng 0 → A, 01 → 0B, . . . là các quy tắc không hợp lệ. Ví dụ 1.10. Các bộ bốn sau là các văn phạm: + G1 = h{0, 1}, {S}, S, {S → 0S1, S → ε}i, + G2 = h{a, b}, {S, A}, S, {S → Ab, A → aAb, A → ε}i, + G3 = h{a, b, c}, {S, A, B, C}, S, {S → ABC, A → aA, B → bB, C → cC, A → a, B → b, C → c}i, + G4 = hΣ, ∆, S, P i, trong đó: Σ = {tôi, anh, chị, ăn, uống, cơm, phở, sữa, café}, 15 ∆ = {h câui, h chủngữi, h vịngữi, hđộngtừ1i, hđộngtừ2i, hdanhtừ1i, hdanhtừ2i, } S = hcâui, P = {h câui → hchủngữih vịngữi, hchủngữi → tôi, hchủngữi → anh, hchủngữi → chị, hvịngữi → hđộngtừ1ihdanhtừ1i, hvịngữi → hđộngtừ2ihdanhtừ2i, hđộngtừ1i → ăn, hđộngtừ2i → uống, hdanhtừ1i → cơm, hdanhtừ1i → phở, hdanhtừ2i → sữa, hdanhtừ2i → café}. Chú ý rằng, nếu các quy tắc có vế trái giống nhau có thể viết gọn lại: hai quy tắc α → β, α → γ có thể được viết là α → β | γ. Chẳng hạn, như trong văn phạm G1 ở thí dụ 1.10, ta có thể viết hai quy tắc của nó dưới dạng S → 0S1 | ε. Định nghĩa 1.2. Cho văn phạm G = hΣ, ∆, S, P i và η, ω ∈ (Σ ∪ ∆)∗ . Ta nói ω được suy dẫn trực tiếp từ η trong G, ký hiệu η `G ω hay ngắn gọn là η ` ω (nếu không sợ nhầm lẫn), nếu tồn tại quy tắc α → β ∈ P và γ, δ ∈ (Σ ∪ ∆)∗ sao cho η = γαδ, ω = γβδ. Điều này có nghĩa là nếu η nhận vế trái α của quy tắc α → β như là từ con thì ta thay α bằng β để được từ mới ω. Định nghĩa 1.3. Cho văn phạm G = hΣ, ∆, S, P i và η, ω ∈ (Σ ∪ ∆)∗ . Ta nói ω được suy dẫn từ η trong G, ký hiệu η |=G ω hay ngắn gọn là η |= ω (nếu không sợ nhầm lẫn), nếu η = ω hoặc tồn tại một dãy D = ω0 , ω1 , . . . , ωk ∈ (Σ ∪ ∆)∗ sao cho ω0 = η, ωk = ω và ωi−1 ` ωi , với i = 1, 2, ..., k. Dãy D = ω0 , ω1 , . . . , ωk được gọi là một dẫn xuất của ω từ η trong G và số k được gọi là độ dài của dẫn xuất này. Nếu ω0 = S và ωk ∈ Σ∗ thì dãy D gọi là dẫn xuất đầy đủ. 16 Nếu ωi được suy dẫn trực tiếp từ ωi−1 bằng việc áp dụng một quy tắc p nào đó trong G thì ta nói quy tắc p được áp dụng ở bước thứ i. Định nghĩa 1.4. Cho văn phạm G = hΣ, ∆, S, P i. Từ ω ∩ Σ∗ được gọi là sinh bởi văn phạm G nếu tồn tại suy dẫn S |= ω. Ngôn ngữ sinh bởi văn phạm G, ký hiệu L(G), là tập hợp tất cả các từ sinh bởi văn phạm G: L(G) = {ωk ∈ Σ∗ |S |=G ω}. Định nghĩa 1.5. Hai văn phạm G1 = hΣ1 , ∆1 , S1 , P1 i và G2 = hΣ2 , ∆2 , S2 , P2 i được gọi là tương đương nếu L(G1 ) = L(G2 ). Ví dụ 1.11. + Xét văn phạm G1 trong thí dụ 1.10. Từ ω = 00001111 được suy dẫn từ S bằng dãy dẫn xuất độ dài 5: S ` 0S1 ` 00S11 ` 000S111 ` 0000S1111 ` 00001111 (có thể viết ngắn gọn là ω = 04 14 ). Bằng việc sử dụng n lần (n ≥ 0) quy tắc 1 rồi quy tắc 2, ta có: S |= 0n 1n . Do đó L(G1 ) = {0n 1n |n ≥ 0}. + Xét văn phạm G2 trong thí dụ 1.10. Sử dụng quy tắc 1, rồi n lần (n ≥ 0) quy tắc 2, sau đó quy tắc 3 để kết thúc, ta có: S ` Ab |= an Abn b ` an bn+1 . Do đó L(G2 ) = {an bn+1 |n ≥ 0}. + Xét văn phạm G3 trong thí dụ 1.10. Sử dụng quy tắc 1, rồi m − 1 lần (m ≥ 1) quy tắc 2, n − 1 lần (n ≥ 1) quy tắc 3, k − 1 lần (k ≥ 1) quy tắc 4 (các quy tắc có thể xen kẽ), sau đó kết thúc bởi các quy tắc 5, 6, 7, ta có: S ` ABC |= am Abn Bck C |= am bn ck . Do đó L(G3) = {am bn ck |m ≥ 1, n ≥ 1, k ≥ 1}. + Dễ dàng thấy rằng: L(G4 ) = {tôi ăn cơm, anh ăn cơm, chị ăn cơm,...}. Ví dụ 1.12. Cho hai văn phạm G3 = hΣ, {S}, S, P 3i, G4 = hΣ, {S}, S, P 4i, 17 trong đó: Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P3 = {S → 1|2|3|4|5|6|7|8|9|S0|S1|S2|S3|S4|S5|S6|S7|S8|S9}, P4 = {S → 0|1|2|3|4|5|6|7|8|9|1S|2S|3S|4S|5S|6S|7S|8S|9S}. Dễ thấy rằng L(G3 ) = {n|n ≥ 1}. Thật vậy, sử dụng k − 1 lần (k ≥ 1) các quy tắc trong nhóm 10 quy tắc cuối của G3 , rồi một quy tắc trong nhóm 9 quy tắc đầu tiên của nó, ta có: S ` Si1 ` Si2 i1 ` . . . ` Sik−1 . . . i2 i1 ` Sik ik−1 . . . i2 i1 , (với i1 , i2 , . . . , ik ∈ Σ), trong đó i1 , i2 , . . . , ik−1 ≥ 0 và ik ≥ 1. Do đó, L(G3 ) = {n|n ≥ 1}. Lập luận như trên, ta nhận được L(G4 ) = {n|n ≥ 0}. Vì vậy, G3 và G4 không tương đương nhau. 1.3. Ngôn ngữ phi ngữ cảnh Định nghĩa 1.6. Một văn phạm G = hΣ, ∆, S, P i được gọi là phi ngữ cảnh (context free) nếu mọi luật sinh trong P có dạng A → x, trong đó A ∈ Σ còn x ∈ (Σ ∩ ∆)∗ . Định nghĩa 1.7. Một ngôn ngữ được gọi là phi ngữ cảnh nếu và chỉ nếu có một văn phạm phi ngữ cảnh G sao cho L = L(G). Ví dụ 1.13. Ngôn ngữ sau là phi ngữ cảnh L = {an bn : n ≥ 0} văn phạm phi ngữ cảnh sinh ra ngôn ngữ này có các quy tắc sinh là: S → aSb|ε. Ví dụ 1.14. Xét văn phạm với các quy tắc sinh: S → aSb|SS|ε. Văn 18
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng