Tài liệu Một số tính chất của ngôn ngữ phi ngữ cảnh

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ====== LÊ THỊ THANH LOAN MỘT SỐ TÍNH CHẤT CỦA NGÔN NGỮ PHI NGỮ CẢNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng Người hướng dẫn khoa học TS. KIỀU VĂN HƯNG HÀ NỘI - 2017 Khóa luận tốt nghiệp Lê Thị Thanh Loan 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. Em xin chân thành cảm ơn! Vĩnh Phúc, tháng 4 năm 2017 Sinh viên Lê Thị Thanh Loan Khóa luận tốt nghiệp Lê Thị Thanh Loan 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. Trong khi làm khóa luận này, em đã 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. Vĩnh Phúc, tháng 4 năm 2017 Sinh viên Lê Thị Thanh Loan Khóa luận tốt nghiệp Lê Thị Thanh Loan MỤC LỤC MỞ ĐẦU ....................................................................................................... 1 Chương 1. Văn phạm phi ngữ cảnh ................................................................ 3 1.1. Văn phạm phi ngữ cảnh ........................................................................... 3 1.1.1. Định nghĩa ............................................................................................ 3 1.1.2. Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh........................................... 4 1.1.3. Cây suy dẫn đầy đủ trong văn phạm phi ngữ cảnh ................................ 5 1.1.4. Quan hệ giữa dẫn xuất và cây suy dẫn .................................................. 6 1.1.5. Văn phạm phi ngữ cảnh đa nghĩa .......................................................... 8 1.1.6. Rút gọn các văn phạm phi ngữ cảnh ..................................................... 9 1.2. Chuẩn hóa văn phạm phi ngữ cảnh ........................................................ 14 1.2.1. Dạng chuẩn Chomsky......................................................................... 14 1.2.2. Dạng chuẩn Greibach ......................................................................... 16 1.3. Bài tập ................................................................................................... 20 Chương 2. Tính chất của ngôn ngữ phi ngữ cảnh ......................................... 26 2.1. Hai bổ đề Bơm ...................................................................................... 26 2.1.1. Bổ đề Bơm cho ngôn ngữ phi ngữ cảnh .............................................. 26 2.1.2. Bổ đề Bơm cho ngôn ngữ tuyến tính .................................................. 30 2.2. Tính đóng của ngôn ngữ phi ngữ cảnh ................................................... 31 2.3. Một vài tính chất khả quyết của ngôn ngữ phi ngữ cảnh ........................ 32 2.4. Bài tập .................................................................................................. 32 KẾT LUẬN VÀ KIẾN NGHỊ ...................................................................... 34 TÀI LIỆU THAM KHẢO ............................................................................ 35 Khóa luận tốt nghiệp Lê Thị Thanh Loan MỞ ĐẦU 1. Lý do chọn đề tài 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... 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ác tính chất và ứng dụng của nó. 2. Mục đích nghiên cứu Tìm hiểu một cách tổng quan về ngôn ngữ sinh bởi văn phạm phi ngữ cảnh, các tính chất của ngôn ngữ phi ngữ cảnh. 3. Đối tượng và phạm vi nghiên cứu Đối tượng: Các kiến thức cơ bản về tính chất của ngôn ngữ phi ngữ cảnh. Phạm vi: Nội dung kiến thức trong phạm vi của lí thuyết ngôn ngữ hình thức. 4. Nhiệm vụ Tìm hiểu về tính chất của ngôn ngữ phi ngữ cảnh. 5. Phương pháp nghiên cứu Phân tích tài liệu có liên quan. 1 Khóa luận tốt nghiệp Lê Thị Thanh Loan Tổng hợp kinh nghiệm bản thân. 6. Cấu trúc khóa luận Ngoài phần mở đầu, kết luận và tài liệu tham khảo nội dung chính của khóa luận bao gồm 2 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ề tính chất của ngôn ngữ phi ngữ cảnh. 2 Khóa luận tốt nghiệp Lê Thị Thanh Loan Chương 1 Văn phạm phi ngữ cảnh 1.1.Văn phạm phi ngữ cảnh Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự nhiên. Ta có thể viết quy tắc cú pháp để diễn tả câu "Mạnh là sinh viên giỏi" như sau: → → →<động từ> → → Mạnh → sinh viên <động từ>→ là →giỏi Các từ trong dấu móc nhọn như , , , ... là các phạm trù cú pháp, cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu sinh ra qua các bước triển khai dần dần theo các quy tắc cú pháp. Đây cũng chính là dạng của các quy tắc sinh trong 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 3 Khóa luận tốt nghiệp Lê Thị Thanh Loan 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ữ cảnh. Ví dụ 1.1Cho văn phạm G1 = <{a,b},{S, A, B},S,P1 >, trong đó: P 1 = {S→AB, A→aA, A→a, B→bB, B→b} G 1 là văn phạm phi ngữ cảnh. Ví dụ 1.2Cho văn phạm G2 = <{0,1},{S},S,P 2 >, trong đó: P 2 = {S→SS, S→0S1, S→1S0, S→u} G 2 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.1Cho 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 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.2Cho 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 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 đủ. 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. 4 Khóa luận tốt nghiệp Lê Thị Thanh Loan Định nghĩa 1.3Cho 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 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) = {ω* | S ╞Gω}. Định nghĩa 1.4Hai 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.3Xét văn phạm G = <{a,b}, {S}, S, S→aSb, S→ab> 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-1b n-1╞ a n b nVậy L(G) chứa các chuỗi có dạng a nb n, hay L(G) = {anbn |n > 1}. 1.1.3. Cây suy dẫn đầy đủ trong văn phạm phi ngữ cảnh Định nghĩa 1.4Cho 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,..., n k 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,..., B k tương ứng thì A→B1B 2 ...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. Ví dụ 1.4Cho văn phạm phi ngữ cảnh: 5 Khóa luận tốt nghiệp Lê Thị Thanh Loan G1=<{a,b,c,+,*,(,)},{S,A},S,{S→S+S | A*A|a|b|c,A→(S+S)|a|b|c}> Cây suy dẫn của từ b+(a+c)*b trong G1là: Hình 1.1Cây suy dẫn của từ ω = b+(a+c)*b trong G1 1.1.4. Quanhệ 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 giờ với mọi A,đặt G A = <, ,S,P>,ta có G A 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ếtthú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,..., b k . Theo định nghĩa của cây suy dẫn, ta có A→b 1b 2...bk hay A╞ ω. 6 Khóa luận tốt nghiệp Lê Thị Thanh Loan 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 G A 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, C 2 ,..., Cm. Gọi α i là kết quả của cây suy dẫn gốc C i . Theo giả thiết quy nạp, α i L(GA). Vì tập các quy tắc trong GA 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 , C 2 ╞ α 2 ,...,C m╞ α m. Sử dụng các suy dẫn này và quy tắc A→B 1 B2 ...B k, ta nhận được: A╞ B 1 B 2...Bk ╞ ω1 C 1 ω 2 C 2...ω mC mω 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╞ ω(ω ≠ ε)trongGA 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. Trước hết, nếu A╞ ω╞ b 1 b2 ...b k (suy dẫn một bước) thì có thể xây dựngmộ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→B1B2...Bk và C1, C 2,..., C m là các ký hiệu không kết thúc trong các B i (1. 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 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.5Văn phạm phi ngữ cảnh sau là nhập nhằng: 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 1.3: 8 Khóa luận tốt nghiệp Lê Thị Thanh Loan Hình 1.3Hai cây suy dẫn khác nhau cho từω = b+a*b+a Cùng với văn phạm G ở trên, văn phạm G’ = <{a, b, +, *}, {S, A}, S, {S→A, S→A+S, A→A*A, A→a, A→b}> là đơn nghĩa và L(G’) = L(G). 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 dạng 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.6Cho 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ý hiệu thừa. 9 Khóa luận tốt nghiệp Lê Thị Thanh Loan 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 mọi 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ảnhG=<,,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 mọi X '' có α,β(’)* để cho S╞αXβ. Chứng minh: Xây dựng tập ’ và ’ như sau: 10 Khóa luận tốt nghiệp Lê Thị Thanh Loan Đư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à ’ . Tập quy tắc P’ được xây dựng như sau: 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.2Mọ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. ĐặtG 1 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.7Cho 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ì 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. 11 Khóa luận tốt nghiệp Lê Thị Thanh Loan Đị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ácquy tắccủ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.6Vă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.8Cho 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→ε). 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ừ 12 Khóa luận tốt nghiệp Lê Thị Thanh Loan rỗng. Định lý 1.4Cho 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 B→ε P thì A là ký hiệu triệt tiêu.  Nếu B→α  P mà a 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→X1X2...Xn  P, X i ()*, 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à ký hiệu triệt tiêu. Ví dụ 1.7 Cho văn phạm phi ngữ cảnh G = <{a, b}, {I, A, B}, I, P> vớitập quy tắc P = {I→AB, A→aA, A→ε, B→bB, B→ε}. Hãy xây dựng văn phạm G’ không có các ε-quy tắc, không có các ký hiệu thừa, sao cho L(G’) = L(G) \{ε}. + Dễ thấy G là không có các ký hiệu thừa. 13 Khóa luận tốt nghiệp Lê Thị Thanh Loan + Cácký hiệu triệt tiêu là A và B. + Tậpquy tắc P’ = {I→AB, I→A, I→B, A→aA, A→a,B→bB,B→b}. Vậy ta có G’ = <{a, b}, {I, A, B}, I, P’> là văn phạm không chứa các εquy tắc Ví dụ 1.8 Văn phạm phi ngữ cảnh G1 =<{a, b, d}, {S, A, B, C, D},S,P1> với tập quy tắc P 1 = {S→ABaC, A→BC, B→b | ε, C→D | ε, D→a}.Xây dựng văn phạm G 1 ’ không có các ε-quy tắc sao cho L(G1) = L(G1) \ {ε}. + Cácký hiệu triệt tiêu là A, B, C. + Tậpquy tắc P1 ’ = {S→AbaC | BaC | AaC | ABa | aC | Aa|Ba |a, A→BC | B | C, B→b, C→D,D→d}. Vậy ta có G1’ = <{a, b, d}, {S, A, B, C, D}, S, P1 ’> là văn phạm không chứa các ε-quy tắc. 1.2. Chuẩn hóa văn phạm phi ngữ cảnh 1.2.1. Dạng chuẩn Chomsky Định nghĩa 1.9Văn phạm phi ngữ cảnh G = <, , S, P> được gọi là văn phạm ở dạng chuẩn Chomsky, nếu mọi quy tắc đều có dạng A→BC hoặcA→a, với A, B, C , a  . Như vậy, có thể nhận xét rằng các văn phạm dạng chuẩn Chomsky sẽ không có các quy tắc thuộc các loại sau: a/. Các ε-quy tắc (các quy tắc rỗng). b/. Các quy tắc đơn, dạng A→B, A, B . c/. Các quy tắc mà vế phải có cả ký hiệu chính và ký hiệu phụ. d/. Các quy tắc có vế phải nhiều hơn hai ký hiệu. Đưa văn phạm phi ngữ cảnh về dạng chuẩn Chomsky Định lý 1.5Đối với văn phạm phi ngữ cảnh tùy ý G = <, , S, P>, luôn tồn tại một văn phạm phi ngữ cảnh ở dạng chuẩn Chomsky G’ = <, ', S, P’> tương đương với nó, tức là L(G) = L(G’). 14 Khóa luận tốt nghiệp Lê Thị Thanh Loan Chứng minh:Theo các định lý 1.2, 1.3 và 1.4 phần trên, ta có thể giả thiết văn phạm G không chứa các ký hiệu thừa, không chứa các ε-quy tắc và không chứa các quy tắc đơn. Để xây dựng văn phạm mới G’ ở dạng chuẩn Chomsky, ta chỉ cần loại bỏ các quy tắc mà vế phải có chứa cả ký hiệu chính và ký hiệu phụ hoặc các quy tắc mà vế phải nhiều hơn hai ký hiệu. Việc loại bỏ các quy tắc không hợp lệ này tiến hành theo hai bước sau: Bước 1: Với các quy tắc vế phải có chứa cả ký hiệu chính và ký hiệu phụ, tức là các quy tắc có dạng A→X1X2 ...Xm, với X i .(1) Xét tất cả các X i trong quy tắc (1), nếu Xi  thì giữ nguyên Xi, nếu Xi = a , ta thêm vào ký hiệu phụ Aa, thay Xi trong quy tắc (1) bởi Aa,và thêm vào quy tắc Aa →a. Lặp lại quá trình trên với tất cả các Xi trong quy tắc (1), quy tắc (1) trở thành: A→Y1Y2 ...Ym, với Yi là các ký hiệu phụ (Yi = Xi nếu X i  , Y i = Ai nếu Xi = a ). Sau bước 1, ta nhận được văn phạm G1 = <, A1, S, P 1> với 1 và P1 nhận được từ  và P sau khi thêm vào các ký hiệu phụ mới và các quy tắc mới như trên. Rõ ràng L(G1) = L(G) mà G1 không chứa các quy tắc mà vế phải có cả ký hiệu chính và ký hiệu phụ. Bước 2: Bây giờ trong G1 cần loại bỏ các quy tắc mà vế phải có độ dài lớn hơn 2, gồm toàn ký hiệu phụ, là các quy tắc dạng: A→Y1Y2...Ymvới m>2, Y 1. Ta thêm m-2 ký hiệu phụ Z 1, Z2,..., Z m-2 vào tập 1 và thêm vào m-2 quy tắc sau đây: AY1Z1 ; Z1Y2Z2; Y2Y3Z3 ; ...; Zm-2Ym-1Zm. Ta nhận được văn phạm mới G2 = <, 2, S, P2> không chứa các quy tắc có vế phải nhiều hơn 2 ký hiệu, không chứa các quy tắc vế phải gồm cả ký hiệu chính và ký hiệu phụ. Dễ dàng chỉ ra rằng L(G2) = L(G1) = L(G), vậy G2 15 Khóa luận tốt nghiệp Lê Thị Thanh Loan chính là văn phạm G’ ở dạng chuẩn Chomsky cần tìm. Ví dụ 1.9Cho văn phạm phi ngữ cảnh G = <{a,b},{S,A,B},S,P>, với tập quy tắc P = {S→A, S→ABA, A→aA, A→aA, A→a, A→B, B→bB, B→b}. Hãy xây dựng văn phạm ở dạng chuẩn Chomsky tương đương với G. Giải: Áp dụng định lý 1.3, ta có thể loại hết các quy tắc đơn trong G, để được văn phạm tương đương mà không chứa quy tắc đơn G1 =<{a,b},{S,A,B},S,P1>, với P1 = {S→ABA, S→aA, S→a, S→bB, S→b, A→aA, A→a, A→bB, A→b, B→bB, B→b}. Bây giờ ta thay tất cả các quy tắc mà vế phải có chứa cả ký hiệu chính và ký hiệu phụ: + Với các quy tắc S→aA, A→aA ta thay a bởi Aa, thêm Aa vào tập ký hiệu phụ mới 2, thêm quy tắc Aa →a vào tập quy tắc mới P2. + Với các quy tắc S→bB, A→bB, B→bB ta thay b bởi Ab, thêm Ab vào tập ký hiệu phụ mới 2, thêm quy tắc Ab →b vào tập quy tắc mới P2. Ta nhận được G2 = <{a, b},{S, A, B, Aa, Ab}, S, P2>, với P2 ={S→ABA, S→AaA, S→a, S→Ab B, S→b, A→AaA, A→a,A→AbB, A→b, B→AbB, B→b} không có quy tắc nào mà vế phải có cả ký hiệu chính và ký hiệu phụ, và rõ ràng G2 ~ G1 ~ G. + Với G2, ta giảm độ dài vế phải các quy tắc có hơn hai ký hiệu: thay quy tắc S→ABA bởi hai quy tắc S→AC, C→BA, và thêm C vào tập ký hiệu phụ. Cuối cùng, ta được văn phạm G 3 = <{a, b},{S, A, B, Sa, Ab,C}, S, P3> với P3 = {S→AC, C→BA, S→Aaa, S→a, S→AbB, S→b, A→AaA, A→a, A→AbB, A→b, B→AbB, B→b} Văn phạm G3 ~ G 2 ~ G1 ~ G, mà G3 ở dạng chuẩn Chomsky. 1.2.2. Dạng chuẩn Greibach Một dạng chuẩn khác của văn phạm phi ngữ cảnh là dạng chuẩn 16