Tài liệu Về otomat đẩy xuống và ngôn ngữ phi ngữ cảnh

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Phạm Thị Thu Hà VỀ OTOMAT ĐẨY XUỐNG VÀ NGÔN NGHỮ PHI NGỮ CẢNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Phạm Thị Thu Hà VỀ OTOMAT ĐẨY XUỐNG VÀ NGÔN NGỮ PHI NGỮ CẢNH Chuyên ngành: Toán học ứng dụng KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Kiều Văn Hưng Hà Nội – Năm 2016 Lời cảm ơn Em xin được bày tỏ lòng biết ơn chân thành tới TS Kiều Văn Hưng, người thầy đã truyền thụ kiến thức, tận tình giúp đỡ, hướng dẫn em trong suốt quá trình học tập, nghiên cứu và hoàn thành khóa luận này. Em xin được gửi lời cảm ơn tới các thầy cô giáo trường Đại học Sư phạm Hà Nội 2, các thầy cô giáo khoa Toán đã giúp đỡ em trong quá trình học tập tại trường và tạo điều kiện cho em hoàn thành đề tài khóa luận tốt nghiệp. Trong quá trình nghiên cứu, không tránh khỏi những thiếu sót và hạn chế. Em kính mong nhận được sự đóng góp ý kiến của các thầy giáo, cô giáo và toàn thể bạn đọc để khóa luận được hoàn thiện hơn. Hà Nội, ngày tháng 05 năm 2016 Sinh viên Phạm Thị Thu Hà Lời cam đoan Em xin cam đoan dưới sự hướng dẫn của thầy giáo Kiều Văn Hưng khóa luận của em được hoàn thành không trùng với bất kì đề tài nào khác. Em cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện khóa luận này đã được cảm ơn và các thông tin thu trích dẫn trong khóa luận đã được chỉ rõ nguồn gốc. Hà Nội, tháng 5 năm 2016 Sinh viên Phạm Thị Thu Hà ii Mục lục Lời mở đầu ii Danh mục các kí hiệu và chữ viết tắt iv 1 Văn phạm phi ngữ cảnh 1.1 1 . . . . . . . . . . . . . . . . . 1 1.1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh . . . . 2 1.1.3 Cây suy dẫn đầy đủ trong văn phạm phi ngữ cảnh 3 1.1.4 Quan hệ giữa dẫn xuất và cây suy dẫn . . . . . . 3 1.1.5 Văn phạm phi ngữ cảnh đa nghĩa . . . . . . . . . 5 1.1.6 Rút gọn các văn phạm phi ngữ cảnh . . . . . . . 7 Chuẩn hóa văn phạm phi ngữ cảnh . . . . . . . . . . . . 12 1.2.1 Dạng chuẩn Chomsky . . . . . . . . . . . . . . . 13 1.2.2 Dạng chuẩn Greibach . . . . . . . . . . . . . . . . 16 1.3 Bổ đề Bơm cho ngôn ngữ phi cảnh . . . . . . . . . . . . 20 1.4 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2 Văn phạm phi ngữ cảnh 2 Otomat đẩy xuống 2.1 32 Mô tả otomat đẩy xuống . . . . . . . . . . . . . . . . . . i 33 2.2 Otomat đẩy xuống không đơn định . . . . . . . . . . . . 35 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 35 2.2.2 Hàm chuyển . . . . . . . . . . . . . . . . . . . . . 36 2.2.3 Hình trạng . . . . . . . . . . . . . . . . . . . . . . 37 2.2.4 Ngôn ngữ đoán nhận bởi otomat đẩy xuống không đơn định . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 Otomat đẩy xuống không đơn định và ngôn ngữ phi ngữ cảnh . . . . . . . . . . . . . . . . . . . . 2.3 2.4 38 40 Otomat đẩy xuống đơn định và ngôn ngữ phi ngữ cảnh đơn định . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Kết luận 51 Tài liệu tham khảo 51 ii Lời mở đầu Những năm gần đây, con người đã đạt được nhiều thành tựu khoa học rực rỡ, một trong những thành tựu đó là sự bùng nổ của ngành khoa học máy tính. Sự phát triển kì diệu của máy tính gắn liền với sự phát triển toán học hiện đại, đó là Toán rời rạc. Toán học rời rạc nghiên cứu các cấu trúc có tính chất rời rạc không liên tục. Toán rời rạc bao gồm các lĩnh vực như quan hệ, lý thuyết đồ thị, ngôn ngữ hình thức và otomat... Lý thuyết ngôn ngữ hình thức là lý thuyết nền tảng cho việc thấu hiểu khái niệm về ngôn ngữ nói chung (cả ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên), và các vấn đề cơ bản về ngôn ngữ như cách xây dựng văn phạm sinh ra ngôn ngữ (xây dựng văn phạm cho ngôn ngữ lập trình, cho quá trình phân tích cú pháp), dịch từ ngôn ngữ lập trình cấp cao sang ngôn ngữ máy. . . Lý thuyết otomat là lý thuyết cơ bản cho việc nghiên cứu các mô hình tự động để làm tiền đề cho sự phát triển đến dạng máy tính số như hiện nay. Ngôn ngữ phi ngữ cảnh là chủ đề quan trọng nhất của lý thuyết ngôn ngữ hình thức, vì nó áp dụng cho ngôn ngữ lập trình. Mục đích của khóa luận này nhằm tìm hiểu rõ hơn về ngôn ngữ phi ngữ cảnh cùng với cơ chế để sinh lớp ngôn ngữ này, đó là các văn phạm phi ngữ cảnh và các otomat có bộ nhớ đẩy xuống. Khóa luận được chia thành hai chương: Chương 1 trình bày về văn phạm phi ngữ cảnh và ngôn ngữ phi ngữ cảnh Chương 2 trình bày về khái niệm otomat đẩy xuống và sự liên kết giữa otomat đẩy xuống và ngôn ngữ phi ngữ cảnh. iii Hà Nội, ngày 04/05/2016 Tác giả khóa luận Phạm Thị Thu Hà iv Danh mục các kí hiệu và chữ viết tắt ∅ tập rỗng x∈M x thuộc tập M x∈ /M x không thuộc tập M ∀ x ∈ M với mọi x thuộc tập M ∃x tồn tại x M ∩N giao của hai tập hợp M và N M ∪N hợp của hai tập hợp M và N Σ∗ tập mọi từ trên bảng chữ cái Σ v Chương 1 Văn phạm phi ngữ cảnh 1.1 Văn phạm phi ngữ cảnh 1.1.1 Định nghĩa Văn phạm phi ngữ cảnh là một bộ sắp thứ tự gồm 4 thành phần: G = <Σ, ∆, S, P>, trong đó: + Σ là một bảng chữ cái, gọi là bảng chữ cái cơ bản (hay bảng chữ cái 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ữ cái, ∆ ∩ Σ = ∅, gọi là bảng ký hiệu phụ (hay bảng chữ cái 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 A → ω, trong đó A ∈ ∆, ω ∈(Σ ∪ ∆). Như vậy, các quy tắc trong văn phạm phi ngữ cảnh có vế trái chỉ chứa một ký hiệu phụ còn vế phải là tùy ý, và được gọi là quy tắc phi ngữ 1 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà cảnh. Ví dụ 1.1. Cho văn phạm G1 = <{a,b}, {S, A, B}, S, P1 >, trong đó: P1 = {S → AB, A → aA, A → a, B → bB, B → b}. G1 là văn phạm phi ngữ cảnh. Ví dụ 1.2. Cho văn phạm G2 = <{0,1},{S},S,P2 >, trong đó: P2 = {S → SS, S → 0S1, S → 1S0, S → ε}. G2 là văn phạm phi ngữ cảnh. 1.1.2 Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh Định nghĩa 1.1. Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P> 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 tồn tại quy tắc α → β ∈ P và γ, δ ∈ (Σ ∪ ∆)∗ sao cho η = γαδ, ω = γβδ. Định nghĩa 1.2. Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P> và η, ω ∈ (Σ ∪ ∆)∗ . Ta nói ω được suy dẫn từ η trong G, ký hiệu η |=G ω hay ngắn gọn là η |= ω, 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. Định nghĩa 1.3. Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P>. Từ ω ∈ Σ∗ được gọi là sinh bởi văn phạm phi ngữ cảnh 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) = {ω ∈ Σ∗ | S |=G ω}. Hai văn phạm G1 = <Σ1 , ∆1 , S1 , P1 > và G2 = <Σ2 , ∆2 , S2 , P2 > được gọi là tương đương nếu L(G1 ) = L(G2 ). Ví dụ 1.3. Xét văn phạm G = <{a,b}, {S}, S, S → aSb, S → ab> 2 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà Bằng cách áp dụng quy tắc sinh thứ nhất n-1 lần và quy tắc sinh thứ hai 1 lần, ta có: S ⊢ aSb|= aaSbb|= a3 Sb3 |=... |= an−1 bn−1 |= an bn Vậy L(G) chứa các chuỗi có dạng an bn , hay L(G) = {an bn |n ≥ 1}. 1.1.3 Cây suy dẫn đầy đủ trong văn phạm phi ngữ cảnh Định nghĩa 1.4. Văn phạm phi ngữ cảnh G= <Σ, ∆, S, P>. Cây suy dẫn đầy đủ trong văn phạm G là một đồ thị hữu hạn có hướng, không có chu trình và thỏa mãn bốn điều kiện sau: 1.Mỗi đỉnh của cây được gán một nhãn là các ký hiệu trong tập Σ ∪ ∆ ∪ {ε}. 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 ∆. 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 Σ. 4. Nếu đỉnh m được gán nhãn là A ∈ ∆, 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 → B1 B2 ...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. 1.1.4 Quan hệ giữa dẫn xuất và cây suy dẫn Định lý 1.1. Cho G= <Σ, ∆, S, P> là văn phạm phi ngữ cảnh và ω ∈ Σ∗ \{ε}. Khi đó ω ∈ L(G) khi và chỉ khi tồn tại một cây suy dẫn đầy đủ trong G có kết quả là ω. Chứng minh. Do ω ̸= ε nên ta có thể giả thiết rằng S → ε ∈ / P . Bây 3 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà giờ với mọi A ∈ ∆, đặt GA = <Σ, ∆, S, P>, ta có GA là văn phạm phi ngữ cảnh. Ta sẽ chứng tỏ rằng ω ∈ L(GA ) khi và chỉ khi tồn tại một cây suy dẫn trong GA có kết quả là ω. Giả sử ω là kết quả của một cây suy dẫn trong GA và n là số ký hiệu không kết thúc trong cây. Bằng quy nạp theo n, ta sẽ chỉ ra rằng ω ∈ L(GA ). Nếu tổng số ký hiệu không kết thúc trong cây là 1, ký hiệu phải là A và là gốc của cây, do đó các con của A phải là các đỉnh được gán bởi các ký hiệu kết thúc, chẳng hạn b1 ,b2 ,..., bk . Theo định nghĩa của cây suy dẫn, ta có A → b1 b2 ...bk hay A |= ω. Giả sử mệnh đề đúng với mọi cây suy dẫn có số ký hiệu không kết thúc là n-1. Xét một cây suy dẫn trong GA có kết quả là ω và trong cây có n ký hiệu không kết thúc. Gọi các con của A theo thứ tự từ trái sang phải là B1 , B2 , ...,Bk . Nếu các đỉnh này đều là lá thì cây gốc A chỉ có một đỉnh có ký hiệu không kết thúc. Giả sử trong các đỉnh này có các đỉnh trong là C1 , C2 , ..., Cm . Xét các cây con mà gốc của nó là C1 , C2 , ..., Cm . Gọi αi là kết quả của cây suy dẫn gốc Ci . Theo giả thiết quy nạp, αi ∈ L(GA ). Vì tập các quy tắc trong GCi chứa trong tập các quy tắc trong GA nên ta có các suy dẫn trong GA là C1 |= α1 , C2 |= α2 ,..., Cm |= αm . Sử dụng các suy dẫn này và quy tắc A → B1 B2 ...Bk , ta nhận được A |= B1 B2 ...Bk |= ω1 C1 ω2 C2 ...ωm Cm ωm+1 |= ...|= ω1 α1 ω2 α2 ...ωm αm ωm+1 Do kết quả của cây suy dẫn trong GA là ω nên ω = ω1 α1 ω2 α2 ...ωm αm ωm+1 hay ω ∈ LG (A). Đảo lại ta cần chứng minh rằng nếu có suy dẫn A |= ω(ω ̸= ε) trong GA thì có thể xây dựng một cây suy dẫn trong GA có kết quả là ω. Mệnh đề này được chứng minh bằng quy nạp theo độ dài của suy dẫn. 4 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà Trước hết, nếu A |= ω = b1 b2 ...bk (suy dẫn một bước) thì có thể xây dựng một cây có gốc là A và các con từ trái sang phải lần lượt được gán các nhãn là b1 ,b2 ,.., bk . Giả sử mệnh đề đúng với mọi suy dẫn có độ dài không lớn hơn n. Cho suy dẫn trong GA là A |= ω có độ dài là n+1. Giả sử quy tắc đầu tiên trong suy dẫn này là A → B1 B2 ...Bk và C1 , C2 ,..., Cm là các ký hiệu không kết thúc trong các Bi (1 ≤ i ≤ k), có nghĩa là B1 B2 ...Bk = ω1 C1 ω2 C2 ...ωm Cm ωm+1 , ở đây Ci |= ωi có độ dài không vượt quá n. Theo giả thiết quy nạp, tồn tại các cây Ti của GCi mà kết quả của nó là αi và do đó ta có thể xây dựng trong GA cây suy dẫn có kết quả là ω như sau: Hình 1.1: Cây suy dẫn có kết quả ω 1.1.5 Văn phạm phi ngữ cảnh đa nghĩa Định nghĩa 1.5. Cho văn phạm phi ngữ cảnh G= <Σ, ∆, S, P>. Ta nói văn phạm G là nhập nhằng hay đa nghĩa nếu tồn tại một xâu ω là kết quả của hai cây suy dẫn khác nhau trong G. Trong trường hợp ngược lại, ta nói G là không nhập nhằng hay đơn 5 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà nghĩa. Một văn phạm phi ngữ cảnh được gọi là nhập nhằng vĩnh cửu nếu không tồn tại văn phạm phi ngữ cảnh đơn nghĩa nào tương đương với nó. Ngôn ngữ do văn phạm G sinh ra gọi là ngôn ngữ nhập nhằng nếu G là văn phạm nhập nhằng. Ví dụ 1.4. Văn phạm phi ngữ cảnh sau là đa nghĩa. G’ = <{a,b,+,*}, {S}, S, {S → S + S, S → S ∗ S, S → a, S → b}> vì xâu ω = b+a*b+a có hai suy dẫn trái khác nhau trong G’ được cho trong hình: Hình 1.2: Hai cây suy dẫn khác nhau cho từ ω = b+a*b+a Ví dụ 1.5. Văn phạm phi ngữ cảnh G1 = <{a, b, c, +, *, (, )}, {E, T, F, I}, E, {E → T , T → F , F → I, E → E + T , T → T ∗ F , F → (E), I → a | b | c}>. Cây suy dẫn của xâu ω = a + b * c được chỉ ra trong hình, không có một cây dẫn xuất nào khác có xâu này. Văn phạm này là đơn nghĩa. 6 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà Hình 1.3: Cây suy dẫn cho từ ω = a + b * c 1.1.6 Rút gọn các văn phạm phi ngữ cảnh Trong một văn phạm phi ngữ cảnh có thể có nhiều yếu tố thừa, chẳng hạn có những ký hiệu không hề tham gia vào quá trình sinh các ngôn ngữ, hoặc có những quy tắc dang A → B chỉ làm mất thời gian trong quá trình hình thành các xâu của ngôn ngữ. Vì lẽ đó cần loại bỏ những yếu tố dư thừa không có ích trong việc sinh ngôn ngữ, sao cho việc loại bỏ đó không làm ảnh hưởng tới quá trình sinh ngôn ngữ. Điều đó có nghĩa là chỉ cần giữ lại các ký hiệu và các quy tắc có ích trong văn phạm G mà chúng thực sự là cần thiết trong quá trình sinh ngôn ngữ mà thôi. Rút gọn các ký hiệu thừa trong văn phạm phi ngữ cảnh Định nghĩa 1.6. Cho văn phạm phi ngữ cảnh G= <Σ, ∆, S, P>. X được gọi là ký hiệu có ích nếu tồn tại suy dẫn S |= αXβ |= ω, trong đó α, β ∈ (Σ ∪ ∆), X ∈ Σ ∪ ∆ và ω ∈ Σ∗ . Nếu ký hiệu X không thỏa mãn điều kiện trên thì X được gọi là ký 7 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà hiệu thừa. Như vậy X là ký hiệu thừa nếu: 1/. Từ X không thể dẫn ra một xâu ω ∈ Σ∗ . Ký hiệu X có tính chất như thế được gọi là ký hiệu vô sinh. 2/. Từ ký hiệu xuất phát S không thể dẫn được một xâu nào có chứa ký hiệu X. Khi đó ta nói ký hiệu X là ký hiệu không đến được. Như vậy một ký hiệu là thừa nếu nó hoặc là ký hiệu vô sinh hoặc là ký hiệu không đến được. Bổ đề 1.1. (Loại ký hiệu vô sinh) Cho văn phạm phi ngữ cảnh G= <Σ, ∆, S, P> với L(G) ̸= ∅. Khi đó tồn tại văn phạm phi ngữ cảnh G’= <Σ, ∆′ , S, P’> tương đương với G sao cho ∀A ∈ ∆′ có một xâu ω ∈ Σ∗ để A |= ω. Chứng minh. Từ tập quy tắc P của G, ta xây dựng ∆′ như sau: + Nếu trong P có quy tắc dạng A → ω với A ∈ ∆, ω ∈ Σ∗ thì kết nạp A vào ∆′ . + Nếu A → X1 X2 ...Xk là quy tắc trong P mà Xi ∈ Σ hoặc Xi là biến đã được kết nạp vào ∆′ thì ta kết nạp A vào ∆′ . Cứ tiếp tục xét các quy tắc trong P, ta sẽ xây dựng các ký hiệu cho tập ∆′ . Vì P là hữu hạn nên quá trình sẽ được dừng lại sau một số hữu hạn bước. Khi đó ta xây dựng được tập ∆′ . Ta xây dựng tiếp cận quy tắc P’ gồm các quy tắc trong P mà các ký hiệu có mặt trong đó đều thuộc tập Σ ∪ ∆′ . Bổ đề 1.2. (Loại ký hiệu không đến được) Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P>. Khi đó tồn tại văn phạm phi ngữ cảnh G’= <Σ′ , ∆′ , S, P’> tương đương với G sao cho ∀X ∈ Σ′ ∪ ∆′ có α, β ∈ (Σ′ ∪ ∆′ )∗ để cho S |= αXβ. 8 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà Chứng minh. Xây dựng tập Σ′ và ∆′ như sau: Đưa ký hiệu S vào ∆′ . Nếu một ký hiệu A đã được kết nạp vào ∆′ và A → α, ở đây α ∈ (Σ′ ∪ ∆′ )∗ thì ta kết nạp các ký hiệu phụ trong α vào ∆′ , còn các ký hiệu kết thúc trong α thì kết nạp vào Σ′ . Thủ tục kết nạp trên sẽ ngừng khi không còn bổ sung thêm được bất kỳ ký hiệu nào nữa vào các tập Σ′ và ∆′ . P’ bao gồm mọi quy tắc trong P mà chứa các ký hiệu thuộc tập Σ′ ∪ ∆′ . Với cách xây dựng đó, ta có L(G) = L(G’), trong đó G’ chỉ gồm các ký hiệu đến được. Định lý 1.2. Mọi ngôn ngữ phi ngữ cảnh khác rỗng đều có thể được sinh ra từ một văn phạm phi ngữ cảnh không có ký hiệu thừa. Chứng minh. Đặt L = L(G) là ngôn ngữ phi ngữ cảnh không rỗng. Đặt G1 là kết quả của việc áp dụng bổ đề 1.1 vào G và G2 là kết quả của việc áp dụng bổ đề 1.2 vào G1 . Giả sử G2 có ký hiệu vô ích X. Theo bổ đề 1.2 ta có S |=G2 αXβ. Vì tất cả các ký hiệu trong G2 đều có trong G1 nên theo bổ đề 1.1 S |=G1 αXβ |=G1 ω với ω là chuỗi ký hiệu kết thúc. Vì vậy không có ký hiệu nào trong dẫn xuất αXβ |=G1 ω bị loại bởi bổ đề 1.2. Vậy X dẫn ra ký hiệu kết thúc trong G2 . Suy ra X là ký hiệu có ích (mâu thuẫn). Vậy văn phạm phi ngữ cảnh G2 không có ký hiệu thừa nào. Rút gọn các quy tắc thừa trong văn phạm phi ngữ cảnh Định nghĩa 1.8. Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P>. Quy tắc trong P có dạng A → B, ở đây A, B∈ ∆, được gọi là quy tắc đơn hay phép đổi tên. Quy tắc đơn có tác dụng làm kéo dài quá trình sinh ra ngôn ngữ, vì 9 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà vậy ta sẽ tìm cách loại quy tắc đơn mà không làm ảnh hưởng tới quá trình sinh ra ngôn ngữ của văn phạm đã cho. Định lý 1.3. Đối với mọi phạm phi ngữ cảnh mà trong tập các quy tắc của nó có quy tắc đơn thì tồn tại một văn phạm phi ngữ cảnh tương đương với nó mà trong tập các quy tắc của nó không chứa quy tắc đơn. Chứng minh. Giả sử G = <Σ, ∆, S, P> là văn phạm phi ngữ cảnh có chứa quy tắc đơn (và không chứa ký hiệu thừa). Ta xây dựng văn phạm phi ngữ cảnh G’ = <Σ, ∆, S, P’> tương đương với G và không chứa quy tắc đơn. Đưa tất cả các quy tắc không đơn của P vào P’. Nếu trong P có quy tắc A → B, với A, B∈ ∆, thì tồn tại suy dẫn S |= αAβ |= αBβ |= α ω β, ở đây α, β ∈ (Σ ∪ ∆)∗ , ω ∈ Σ∗ do ∆ gồm các ký hiệu không thừa. Vậy thay cho A → B, ta đưa vào P’ quy tắc S → αAβ và A → ω đều là các quy tắc không đơn nhưng chức năng sinh ngôn ngữ tương đương với quy tắc A → B. Ví dụ 1.6. Văn phạm phi ngữ cảnh G = <{a,+,*}, {S,A,B}, S, {S → S + A, S → A, A → A ∗ B, S → a, A → B, B → a}> tương đương với văn phạm phi ngữ cảnh sau không còn các quy tắc đơn. G = <{a,+,*}, {S,A,B}, S, {S → S + A, A → A ∗ B, B → a, S → a,S → A ∗ B, A → a, S → a}>. Định nghĩa 1.9. Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P>, nếu trong P có quy tắc A → ε, A ∈ ∆, thì ta nói G có ε-quy tắc. Nếu L(G) không chứa từ rỗng ε thì có thể loại hết các ε-quy tắc trong P để được một văn phạm mới tương đương với G; còn nếu trong L(G) có chứa từ rỗng ε, thì không thể loại hết các ε-quy tắc khỏi G (ít nhất trong G phải chứa quy tắc S → ε). 10 Khóa luận tốt nghiệp Đại học Phạm Thị Thu Hà Các ε-quy tắc cũng làm văn phạm phi ngữ cảnh trở nên cồng kềnh, thiếu chính xác. Định lí dưới đây cho phép loại bỏ các ε-quy tắc trong văn phạm phi ngữ cảnh để được một văn phạm mới tương đương, chỉ sai khác một từ rỗng. Định lý 1.4. Cho văn phạm phi ngữ cảnh G = <Σ, ∆, S, P>, giả sử L = L(G). khi đó tồn tại một văn phạm phi ngữ cảnh G’ = <Σ′ , ∆′ , S, P’> không chứa các ε-quy tắc sao cho L(G’) = L(G) \ {ε}. Chứng minh. Theo định lý 1.2, ta luôn giả thiết văn phạm G là không chứa các ký hiệu thừa. Ta sẽ xây dựng G’ không chứa các quy tắc rỗng theo các bước sau: 1/. Tìm tất cả các ký hiệu triệt tiêu (nullable symbol) theo thủ tục: • Nếu A → ε ∈ P thì A là ký hiệu triệt tiêu. • Nếu B → α ∈ P mà α là một xâu gồm toàn ký hiệu triệt tiêu thì B là ký hiệu triệt tiêu. • Lặp lại các bước trên cho đến khi không tìm thêm được ký hiệu triệt tiêu nào nữa. 2/. Xây dựng tập quy tắc P’ • Loại tất cả các quy tắc rỗng trong P (có dạng A → ε). • Tập quy tắc mới P’ được xác định như sau: Nếu A → X1 X2 ...Xn ∈ P , Xi ∈ (Σ∪∆)∗ , thì đưa vào P’ tất cả các quy tắc dạng A → α1 α2 ...αn sao cho: a/. Nếu Xi không phải ký hiệu triệt tiêu thì αi = Xi , (giữ nguyên Xi ) b/. Với các Xi là ký hiệu triệt tiêu thì mỗi lần thay một tập con của các ký hiệu triệt tiêu này bởi các ký hiệu rỗng ε để được một quy tắc mới. c/. Không thay tất cả các αi bởi các ký hiệu rỗng, dù mọi Xi đều là 11