Một số bài toán không giải được đối với ngôn ngữ tuyến tính - Nguyễn Xuân Dũng

42 Tạp chí Kinh tế - Kỹ thuật MỘT SỐ BÀI TỐN KHƠNG GIẢI ĐƯỢC ĐỐI VỚI NGƠN NGỮ TUYẾN TÍNH Nguyễn Xuân Dũng* TĨM TẮT Việc nghiên cứu về tính khả giải của các bài tốn (hoặc các lớp bài tốn) đĩng một vai trị rất quan trọng khơng chỉ đối với sự phát triển của Tốn học nĩi riêng mà cịn ảnh hưởng lớn đến sự phát triển của khoa học cơng nghệ nĩi chung. Trong bài này chúng tơi tiến hành nghiên cứu về tính khả giải của một số bài tốn trong lý thuyết ngơn ngữ hình thức. Cụ thể là, chúng tơi sẽ chứng minh các bài tốn sau đây là khơng giải được đối với ngơn ngữ tuyến tính: Bài tốn tương đương của hai ngơn ngữ tuyến tính bất kỳ. Bài tốn đồng nhất của một ngơn ngữ tuyến tính với một ngơn ngữ chính quy. Bài tốn liệu cĩ hay khơng L = Σ*, đối với ngơn ngữ tuyến tính L cho trước trên bảng chữ cái Σ. Kỹ thuật - Cơng nghệ * TS. Trưởng Khoa Kỹ Thuật – Cơng nghệ, Trường Đại học Kinh tế - Kỹ thuật Bình Dương Định nghĩa 1: Văn phạm tuyến tính là văn phạm mà mỗi luật sinh của nĩ thuộc một trong các dạng sau: A → uBv, A → uB hoặc A → u với A, B là các ký hiệu khơng kết thúc và u, v là các xâu ký hiệu kết thúc. Định nghĩa 2: Cho A = u 1 , u 2 , , u n và B = v 1 , v 2 , , v n là hai danh sách của các xâu trong Σ*. Cho K = { a 1 , a 2 , , a n } là tập n ký hiệu khác nhau khơng cĩ trong Σ. Ta định nghĩa G A = ({S A }, T, P A , S A ) và G B = ({S B }, T, P B , S B ) với T = Σ ∪ K và P A , P B được định nghĩa như sau: Với mỗi i từ 1 đến n, P A chứa các luật sinh dạng: S A → uiSAai và SA → uiai và P B chứa các luật sinh dạng S B → viSBai và SB → viai Đặt L A = L(G A ) và L B = L(G B ), hay ta cĩ thể biểu diễn dưới dạng L A = { 1121 ...... iiiiii aaauuu mmm − | m ≥ 1 và 1 ≤ i m ≤ n} L B = { 1121 ...... iiiiii aaavvv mmm − | m ≥ 1 và 1 ≤ i m ≤ n} Bổ đề 1: Cho L 1 và L 2 là hai ngơn ngữ tuyến tính bất kỳ trên Σ và cho u, v là hai xâu bất kỳ. Khi đĩ L 1 ∪ L 2 và uL 1 v cũng là các ngơn ngữ tuyến tính trên Σ. Chứng minh: Ta chỉ cần chỉ ra các văn phạm tuyến tính sinh ra các ngơn ngữ đĩ. a. Khơng mất tổng quát ta cĩ thể giả thiết rằng L 1 = L(G 1 ) và L 2 = L(G 2 ) Với G 1 = (N 1 , Σ, P 1 , S 1 ) và G 2 = (N 2 , Σ, P 2 , S 2 ) là các văn phạm tuyến tính và N 1 ∩N 2 =. Ta sẽ xây dựng một văn phạm tuyến tính mới sinh ra ngơn ngữ L 1 ∪ L 2 như sau: G = (N 1 ∪ N 2 ∪ {S}, Σ, P 1 ∪ P 2 ∪ {S → S 1 | S 2 }, S) với S là ký hiệu mới khơng thuộc tập N 1 43 Một số bài tốn . . . ∪ N 2 . Từ cách xây dựng văn phạm G ta thấy rằng L(G) = L(G 1 ) ∪ L(G 2 ) = L 1 ∪ L 2 b. Ta sẽ xây dựng văn phạm tuyến tính sinh ra ngơn ngữ uL 1 v như sau: G = (N 1 ∪ {S}, Σ ∪ K, P 1 ∪ {S → uS 1 v}, S) Từ cách xây dựng dễ dàng thấy rằng L(G) = uL 1 v. Định nghĩa 3: Hệ Post (Post correspondence system - PCS) là cặp <A, B>, với A = u 1 , , u n , B = v 1 , , v n Với số tự nhiên n ≥ 1 nào đĩ và các từ khác rỗng u 1 , , u n , v 1, , v n Σ*. Định nghĩa 4: Cho là một PCS bất kỳ trên bảng chữ X; A = u 1 , , u n , B = v 1 , , v n và K = {a 1 , , a n } là tập các ký hiệu khác nhau khơng thuộc X. Ta định nghĩa các văn phạm sau: G A = ({S A }, Σ, P A , S A ) và G B = ({S B }, Σ, P B , S B ) với Σ = X ∪ K cịn P A và P B được xác định như sau: P A : S A → uiSAai | uiai , 1 ≤ i ≤ n P B : S B → viSBai | viai , 1 ≤ i ≤ n Ta ký hiệu L A = L(G A ) và L B = L(G B ). Hiển nhiên L A và L B là các ngơn ngữ tuyến tính phi ngữ cảnh trên Σ = X ∪ K . Ngồi ra L A = { 1121 ...... iiiiii aaauuu mmm − | m ≥ 1 và 1 ≤ i m ≤ n} L B = { 1121 ...... iiiiii aaavvv mmm − | m ≥ 1 và 1 ≤ i m ≤ n} Bổ đề 2: - L A cũng là ngơn ngữ tuyến tính trên Σ. Chứng minh: Từ định nghĩa 4 ta thấy rằng L A ⊆ X*K*, do đĩ mỗi từ w ∉ L A chỉ khi thoả một trong hai trường hợp sau: 1. w ∉ X*K* 2. w ∈X*K* và w∉ L A Tập tất cả các từ trong trường hợp 1 là chính qui vì nĩ là phần bù của tập chính qui. Ta chỉ cịn cần chỉ ra rằng tập tất cả các từ trong trường hợp 2 là tuyến tính, vì theo bổ đề 1 hợp của hai ngơn ngữ tuyến tính là ngơn ngữ tuyến tính. Trước tiên ta để ý là một từ bất kỳ trong trường hợp 2, nghĩa là w ∈X*K* và w∉ L A , khi và chỉ khi w cĩ dạng sau: w = 1121 ...... iiiiii aauauuu mmm − (*) với ∈ ji u A (1 ≤ j ≤ k) nào đĩ, ∈ li a K (1 ≤ l ≤ m) với bất kỳ k ≥ 0, m ≥ k , u ∈ Σ* và u k+ 1 khơng phải là tiền tố của u. Trong trường hợp k = 0 ta địi hỏi là u ≠ e (xâu rỗng) và m ≥ 1. Từ dạng tổng quát của từ w thoả mãn điều kiện 2 trong (*) ta sẽ xem xét các trường hợp cụ thể sau: Trường hợp 1: k = 0, u ≠ e , m ≥ 1 Trong trường hợp này từ w cĩ thể viết như sau: w = 11 ... iii aaua mm − (**) và xâu u khơng cĩ dạng u = vu li với mọi v ∈ X* . Từ lý do đĩ với mỗi 1 ≤ i ≤ n ta sẽ xét các trường hợp con sau: 1 a ) | u | | u i | Ta thấy rằng, với mỗi ui ∈ A số các từ trong X* cĩ độ dài nhỏ hơn | u i | là hữu hạn. Với mỗi i l i l i i aAuS →1 , với l iu là từ bất kỳ trong X* mà liu iu jii aAA 11 → | ja đối với 1 ≤ j ≤ n bất kỳ. 44 Tạp chí Kinh tế - Kỹ thuật Hiển nhiên, mỗi văn phạm iG1 (1 ≤ i ≤ n) là văn phạm tuyến tính. Ta ký hiệu )( 1 11  n i iGLL = = Ngơn ngữ L 1 là tuyến tính theo bổ đề 1. Ngồi ra, cĩ thể dễ dàng khẳng định L 1 là tập tất cả các từ trong trường hợp 1 a . 1 b ) iuu ≥ Từ địi hỏi trong (**) u khơng cĩ dạng vui1 , với v ∈ X*, ta sẽ xét trường hợp này như sau: Với mỗi 1 ≤ i ≤ n ta cĩ thể viết lại từ u trong dạng sau: u = yiv với v ∈ X* nào đĩ, yi ≠ ui và |yi|=|ui|. Từ hạn chế sau cùng đối với yi ta thấy rằng, với mỗi i số các yi như vậy là hữu hạn. Bây giờ ta sẽ xây dựng văn phạm sau: },,({ 2 22 i ii ASG = Σ, ), 22 ii SP Tập các luật sinh iP2 được tạo nên từ các qui tắc sau: i ij i i aAyS 22 → với bất kỳ *Xy j i ∈ với j iy ≠ ui và | j iy | = |ui| 22 ii bSA → | aAi 2 với bất kỳ b ∈ X , a ∈ K bAi → 2 | a với bất kỳ b ∈ X , a ∈ K Ta ký hiệu )( 1 22  n i iGLL = = Từ việc mỗi văn phạm iG2 tuyến tính suy ra tính tuyến tính của ngơn ngữ L 2 . Theo cách xây dựng các văn phạm iG2 ta dễ dàng thấy rằng L 2 là tập tất cả các từ trong X*K* thoả mãn các điều kiện 1 b . Trường hợp 2: k > 0 Ở đây ta sẽ phân ra thành 3 trường hợp con. 2 a ) u = e và m ≥ k+1 Trong trường hợp này từ w sẽ như sau w = 1121 ...... iiiiii aaauuu mmm − Ta sẽ xây dựng văn phạm tuyến tính sinh ra tất cả các từ thuộc Σ* thoả mãn các điều kiện của trường hợp 2 a như sau: G 3 = ({S 3 , A 3 }, Σ, P 3 , S 3 ) Với P 3 được tạo nên từ các luật sinh sau: S 3 → u j S 3 a j | A 3 a j cho tất cả u j ∈A, a j ∈ K, 1 ≤ j ≤ n. A 3 → A 3 a j | a j cho bất kỳ 1 ≤ j ≤ n, a j ∈ K. Ta ký hiệu L 3 = L(G 3 ) và thấy rằng L 3 là ngơn ngữ tuyến tính và ngồi ra chứa tất cả các từ thuộc trường hợp 2 a . Một cách tương tự, ta cĩ trường hợp sau: 2 b ) u ≠ e và m = k. Trường hợp này tương tự như 2 a theo nghĩa “đối xứng”. Từ w cĩ thể viết như sau: w = 1121 ...... iiiiii aauauuu mmm − Bằng lập luận tương tự như trong trường hợp trước ta cĩ thể xây dựng văn phạm tuyến tính sinh ra tất cả các từ trong trong trường hợp 2 b như sau: G 4 = ({S 4 , A 4 }, Σ, P 4 , S 4 ) Với P 4 được tạo nên từ các luật sinh sau: S3 → ujS4aj | bA4 cho tất cả b ∈ X, 1 ≤ j ≤ n. 45 Một số bài tốn . . . A 3 → bA 4 | b cho mỗi b ∈ X Ký hiệu L 4 = L(G 4 ). 2 c ) u ≠ e và m ≥ k. Trường hợp này cĩ thể xảy ra hai khả năng sau: 2 c1 ) |u| |ui| với mỗi i, 1 ≤ i ≤ n. Số các từ trong X* sao cho |u| |ui| là hữu hạn. Từ đĩ ta cĩ thể xây dựng văn phạm tuyến tính sinh ra tập các từ trong trường hợp 2 c1 như sau: },,({ 555 iii ASG = Σ, ), 55 ii SP Với iP5 chứa các luật sinh sau: j i j i aSuS 55 → cho mỗi 1 ≤ j ≤ n ii l i i aAuS 55 → cho mỗi l iu mà liu iu jii aAA 55 → | aj cho mỗi 1 ≤ j ≤ n Ta ký hiệu )( 1 55  n i iGLL = = Rõ ràng L 5 là ngơn ngữ tuyến tính và chứa tất cả các từ trong trường hợp 2 c1 . Sau cùng, ta sẽ xét trường hợp cuối sau: 2 c2 ) | u | | ui | Từ w cĩ thể được viết lại dưới dạng u = l iy v, với v nào đĩ sao cho v X* và i l i uy ≠ , i l i uy = . Với mỗi ui số các l iy như vậy là hữu hạn. Từ đây ta cĩ thể xây dựng văn phạm tuyến tính sinh ra tập các từ trong trường hợp 2 c2 như sau: },,({ 666 iii ASG = Σ, ), 66 ii SP Với iP6 chứa các luật sinh sau: j i j i aSuS 56 → cho mỗi 1 ≤ j ≤ n ii l i i aAyS 66 → cho mỗi l iy mà l iy ≠ ui và liy = iu 66 ii bAA → | iA6 a | a | b cho mỗi aK, b X bất kỳ. Ta ký hiệu )( 1 66  n i iGLL = = Là tuyến tính và chứa tất cả các từ trong trường hợp 2 c2 . Ta đã xét xong tất cả các khả năng của các từ trong X*K* mà khơng thuộc ngơn ngữ L A và thấy rằng tập tất cả các từ như vậy là tuyến tính trên Σ. Kết hợp trường hợp này với trường hợp 1 ta cĩ phần bù của ngơn ngữ tuyến tính L A cũng là ngơn ngữ tuyến tính trên Σ = X K. Trên cơ sở của kết quả vừa nhận được ta cĩ thể chứng minh về tính khơng giải được của một số bài tốn trên lớp ngơn ngữ tuyến tính. Định lý 1: Cho L là một ngơn ngữ tuyến tính bất kỳ trên bảng chữ Σ, khi đĩ bài tốn, liệu L = Σ* Chứng minh: Giả sử là một PCS bất kỳ theo định nghĩa 4. Khi đĩ L A và L B là các ngơn ngữ tuyến tính trên Σ. Theo bổ đề 2 các ngơn ngữ -L A và –L B cũng là các ngơn ngữ tuyến tính trên Σ, do đĩ –L A -L B cũng là các ngơn ngữ tuyến tính trên Σ. Ta cĩ –L A -L B = Σ* = (X K)* chỉ khi –L A -L B = . Đẳng thức sau cùng tồn tại chỉ khi PCP khơng cĩ nghiệm, nhưng bài tốn này 46 Tạp chí Kinh tế - Kỹ thuật là khơng giải được. Từ đây suy ra bài tốn, liệu một ngơn ngữ tuyến tính bất kỳ L trên bảng chữ Σ, L = Σ* là khơng giải được. Từ việc Σ* là ngơn ngữ tuyến tính ta cĩ các kết quả sau. Định lý 2: Cho L là ngơn ngữ tuyến tính bất kỳ trên Σ, R là ngơn ngữ chính qui bất kỳ trên Σ. Bài tốn, L = R là khơng giải được. Định lý 3: Cho L 1 và L 2 là hai ngơn ngữ tuyến tính bất kỳ trên Σ. Khi đĩ bài tốn, L 1 = L 2 là khơng giải được. TÀI LIỆU THAM KHẢO [1] Hopcroft E, Aho A.V, Ullman J.D, Formal Languages and Their Relation to Automata. Addison – Wesley, Reading, Mass. 1969. [2] Aho A.V, Ullman J.D. Theory of Parsing, Translation and Compiling. V1. Prentice Hall 1972.