Giáo trình Lý thuyết, ngôn ngữ hình thức và Otômat

qua bộ phân tích từ vựng, bảng danh biểu sẽ chứa các thông tin sau: Chỉ số Token Lexeme Các thông tin khác 1 id COST biến thực 2 id PRICE biến thực 3 id TAX biến thực 4 Num 65 hằng số nguyên Bảng danh biểu Nếu bộ phân tích từ vựng nhận tiếp các chuỗi ký tự của chương trình nhập, để nhận dạng token, thì bảng danh biểu cũng thường xuyên được truy xuất. Hành vi truy xuất nhằm hai mục đích: nếu danh biểu vừa được nhận dạng đã được lưu chứa trong bảng danh biểu thì phần thứ hai của token là dữ liệu sẽ được cập nhật bằng chỉ số của danh biểu đó trong bảng danh biểu. Thí dụ 5: Với phát biểu trong Thí dụ 3, COST có chỉ số là 1 trong bảng danh biểu, COST lại xuất hiện trong chuỗi nhập sau: y:=COST∗2.0 Chuỗi xuất ra của bộ phân tích từ vựng là: id5:=id1∗num6 ⇔(id, 5):=(id, 1)∗(num, 6) Trong trường hợp này COST không cất vào bảng danh biểu nữa, nhưng bộ phân tích từ vựng sẽ đẩy ra token (id, 1), 1 là vị trí COST đã được cất trong bảng danh biểu trước đó. Bảng danh biểu thường xuyên được truy xuất để thêm hoặc truy xuất các token, do đó phải thoả mãn hai điều kiện: 1. Thực hiện nhanh các thao tác thêm token, hoặc các thông tin của token. 2. Có khả năng truy xuất nhanh các thông tin của một token. 5.2.4. Phát hiện và thông báo lỗi: Ở mỗi giai đoạn của quá trình biên dịch một chương trình nguồn đều có thể có lỗi. Như vậy sau khi phát hiện một lỗi, trình biên dịch xem xét lỗi đó xem có 83 tiếp tục quá trình dịch hay không. Tất nhiên, nếu một trình biên dịch mà ngay khi phát hiện lỗi đầu tiên đã dừng chương trình thì không hữu hiệu. Trong giai đoạn phân tích từ vựng và cú pháp thường xuất hiện nhiều lỗi do trình biên dịch phát hiện. Trong lúc phân tích từ vựng, lỗi được phát hiện khi phần còn lại trên băng nhập không thể tạo nên token. Lỗi xảy ra khi bộ phân tích cú pháp không thể xây dựng cấu trúc cú pháp cho chuỗi token cho trước. Lỗi cũng có thể được phát hiện trong quá trình phân tích ngữ nghĩa, khi trình biên dịch kiểm tra kiểu dữ liệu của hai toán hạng thuộc một phép toán không phù hợp. Chẳng hạn, một toán hạng thuộc kiểu dãy, cộng với một toán hạng là tên của chương trình con. 5.2.5. Phân tích cú pháp (Syntactic analysis parsing): Chuỗi xuất ra từ bộ phân tích từ vựng là các token có dạng (loại token, dữ liệu), sẽ là chuỗi nhập vào bộ phân tích cú pháp. Bộ phân tích cú pháp chỉ xét thành phần thứ nhất của token là loại token. Sự phân tích cú pháp là một quá trình, trong quá trình này chuỗi các token sẽ được kiểm tra xem có thể được biểu diễn bằng cấu trúc cú pháp của ngôn ngữ lập trình cho trước hay không? Nếu tồn tại một cấu trúc cú pháp cho chuỗi nhập thì cấu trúc được sinh ra đó chính là kết quả của quá trình phân tích cú pháp. Ở giai đoạn sinh mã, cấu trúc cú pháp sẽ được xem xét để từ đó sinh ra mã cho chuỗi ký tự của chương trình nguồn. Thí dụ 6: Với phát biểu trong Thí dụ 3, kết quả của quá trình phân tích từ vựng: COST:=(PRICE+TAX)∗65 id1:=(id2+id3)∗num4Phân tích từ vựng và kết quả của quá trình phân tích cú pháp là: id1:=(id2+id3)∗num4 Phân tích cú pháp n3 id1 n2:= ∗ n1 num4 + id2 id3 Cây cú pháp của phát biểu COST:=(PRICE+TAX)∗65 Vậy, kết quả của quá trình phân tích cú pháp của một chuỗi nhập là cấu trúc cú pháp được biểu diễn bằng cấu trúc cây. Cây để biểu diễn cấu trúc cú pháp của một chuỗi nhập được gọi là cây cú pháp hay cây phân tích. Với một chuỗi token là chuỗi nhập và tập luật sinh cho trước, bộ phân tích cú pháp sẽ tự động tìm ra cây 84 cú pháp cho chuỗi nhập. Khi cây cú pháp được xây dựng xong thì quá trình phân tích cú pháp của chuỗi nhập cũng kết thúc thành công. Ngược lại, nếu bộ phân tích cú pháp áp dụng tất cả các luật sinh hiện có, nhưng không thể xây dựng được cây cú pháp của chuỗi nhập cho trước thì bộ phân tích cú pháp sẽ ra thông báo rằng chuỗi nhập không được viết đúng cú pháp của ngôn ngữ lập trình. Nhìn vào cây cú pháp ở trên với các nhãn của các nút n1, n2, n3 ta thấy được trình tự thực hiện: (1) n1 là nút miêu tả phép toán: id2 + id3 (PRICE+TAX) (2) n2 miêu tả phép toán: n1 ∗ num4 (kết quả ở (1) ∗ 65) (3) là phép toán: id1 := n2 (tức là gán kết quả của phép (1) ∗ 65 vào biến COST) Ta thấy rằng dấu ‘(’ và ‘)’ không hiện diện trên cây cú pháp, song việc thực hiện phép toán ở n1: id2 + id3 trước phép nhân với num4 đã chứng tỏ sự có mặt của chúng. 5.2.6. Phân tích ngữ nghĩa: Sau giai đoạn phân tích cú pháp, cấu trúc cú pháp của chuỗi nhập sẽ được bộ phân tích ngữ nghĩa xử lý. Bộ phân tích ngữ nghĩa sẽ kiểm tra lỗi về ngữ nghĩa.. Một nhiệm vụ quan trọng mà bộ phân tích ngữ nghĩa thực hiện là kiểm tra loại dữ liệu. Dựa trên cây cú pháp, bộ phân tích ngữ nghĩa sẽ xử lý từng phép toán. Với mỗi phép toán, nó sẽ xét các toán hạng xem loại dữ liệu của chúng có cho phép để tham gia vào phép tính đó không (nói cách khác loại dữ liệu của các toán hạng trong phép toán cụ thể, có được ngôn ngữ lập trình định nghĩa không). Thí dụ 7: a + 1 với a là biến thuộc loại dữ liệu số thực, 1 là thuộc loại luận lý. Vậy phép cộng không thể thực hiện với hai toán hạng loại số thực và loại luận lý. Hoặc: a + n với a là số thực và n là số nguyên Khi kiểm tra thấy hai toán hạng của phép cộng một có trị thực, một có trị nguyên thì hầu hết các trình biên dịch sẽ chuyển trị của toán hạng n sang biểu thức số thực, cụ thể nếu n có trị là 10 thì trị 10 sẽ được chuyển sang trị thuộc loại thực 10.0 để cộng với trị của a. n3 85 id1 := n2 n1 ∗ intoreal (65) id2 + id3 PRICE TAX 65.0 Với phát biểu trong Thí dụ 3, trị 65 sẽ được chuyển sang số thực. Cây cú pháp khi xử lý ngữ nghĩa sẽ có dạng như trên. 5.2.7. Sinh mã trung gian: Sau giai đoạn phân tích cú pháp và ngữ nghĩa, một số trình biên dịch đã tạo ra sự biểu diễn trung gian của chương trình nguồn. Sự biểu diễn trung gian của chương trình nguồn được hiểu như là chương trình của máy tính trừu tượng (abstract machine). Ngôn ngữ được dùng cho máy trừu tượng là mã trung gian. Mã trung gian có hai đặc điểm quan trọng: dễ được sinh ra và dễ chuyển sang mã đối tượng của chương trình đích. Với Thí dụ 3, kết quả của giai đoạn sinh mã trung gian có dạng: temp p1 := intoreal (65) temp p2 := id2 + id3 (1) temp p3 := temp p2 ∗ temp p1 id1 := temp p3 5.2.8. Tối ưu mã trung gian: Giai đoạn này sẽ thu giảm một số bước trong mã trung gian nhằm làm cho khi sinh ra mã đối tượng thì thời gian thực thi mã đối tượng sẽ ngắn hơn. Bước sinh mã sẽ dùng cây cú pháp đã được xử lý ngữ nghĩa (đã qua bước phân tích ngữ nghĩa) để sinh mã trung gian. Cách làm thông thường như sau:cứ ứng với nút là toán tử sẽ sinh ra mã trung gian như ở (1). Tuy vậy, có cách tốt hơn là với (1) chỉ cần hai mã trung gian mà thôi. temp p1 := id2 + id3 (2) id1 := temp p1 + 65.0 Việc thu giảm như trên sẽ được thực hiện ở bước tối ưu mã. Bước chuyển số nguyên sang số thực sẽ được thực hiện ngay trong thời gian dịch, do đó phép toán intoreal sẽ được bỏ đi. Xem lại (1), ta thấy ở mã thứ tư id1 := temp p3, với temp p3 chỉ dùng có một lần là gán trị vào id1, do đó có thể ghép mã thứ 3 và thứ 4 thành mã thứ 2 của (2). Còn rất nhiều trường hợp khác mà trình biên dịch thực hiện tối ưu mã. Ở đây một vấn đề nảy sinh là thực hiện tối ưu mã trong thời gian biên dịch sẽ làm thời gian dịch tăng lên trong giai đoạn này. Tuy nhiên một số trường hợp tối ưu mã cho phép nếu thời gian thực thi của chương trình đích được rút ngắn mà không làm sự biên dịch quá lâu. 5.2.9. Sinh mã đối tượng: Giai đoạn cuối của trình biên dịch là sinh mã đối tượng. Mã đối tượng có thể là mã máy định vị lại địa chỉ hoặc mã hợp ngữ. 86 Thí dụ 8: Ta sử dụng hai thanh ghi 1 và 2, để dịch mã trung gian (2) sang mã hợp ngữ: movF id2, R1 movF id3, R2 addF R2, R1 (3) mulF # 65.0, R1 movF R1, id1 Lưu ý rằng movF, addF, mulF là phép tính với số thực. Chỉ thị đầu thực hiện chuyển trị từ vị trí nhớ có tên PRICE, thuộc loại token id2 vào thanh ghi R1. Chỉ thị thứ hai thực hiện chuyển trị ở vị trí nhớ có tên TAX thuộc loại token id3 vào thanh ghi R2. Chỉ thị thứ ba thực hiện phép cộng nội dung hai thanh ghi R1 và R2, kết quả phép toán được cất trong R1. Chỉ thị thứ tư thực hiện phép nhân hằng có trị số thực 65.0 với trị nằm trong thanh ghi R1. Chỉ thị cuối cùng chuyển nội dung trong thanh ghi R1 vào vị trí nhớ có tên COST thuộc loại token id1. 5.3. CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH. Các phần trước của chương này ta có nói chuỗi ký tự nhập vào trình biên dịch là văn bản của chương trình nguồn. Đúng vậy, song văn bản đó lại có thể là sản phẩm đầu ra của một hoặc nhiều bộ tiền xử lý (preprocessor) và sản phẩm đầu ra của trình biên dịch có thể lại tiếp tục được xử lý trước khi trở thành mã máy của máy tính thật. Trong phần này ta sẽ nói tới các mối liên quan đó. 5.3.1. Bộ tiền xử lý: Bộ tiền xử lý sẽ tạo ra chuỗi nhập vào trình biên dịch. Bộ tiền xử lý thực hiện các chức năng sau: 1. Xử lý macro (macro processing). Bộ tiền xử lý có thể cho phép người sử dụng định nghĩa các macro. Macro được hiểu là cách viết ngắn gọn cho cấu trúc dài hơn. 2. Chêm tập tin (file inclusion). Bộ tiền xử lý có thể “nhét” các tập tin vào chương trình văn bản. Chẳng hạn, tiền xử lý ngôn ngữ C sẽ “nhét” nội dung của tập tin vào thay thế cho phát biểu # include khi nó xử lý một tập tin có chứa phát biểu trên. 3. Bộ xử lý hoà hợp (Rational processor). Bộ tiền xử lý loại này sẽ tạo nên sự hoà hợp giữa ngôn ngữ cổ điển với những cấu trúc điều khiển, cấu trúc dữ liệu hiện đại hơn.. Chẳng hạn, bộ tiền xử lý giúp cho người sư dụng có thể dùng các phát biểu có cấu trúc như while, if trong ngôn ngữ lập trình, mà tự bản thân ngôn ngữ đó không có các phát biểu trên. Thực tế các phát biểu while, if chính là các macro, khi người sử dụng viết một chương trình trong ngôn ngữ cổ điển có dùng tới hai loại phát biểu có cấu trúc trên và cần biên dịch ra ngôn ngữ máy thì bộ tiền xử lý sẽ làm 87 việc trước. Tất cả nơi nào có hai phát biểu while, if sẽ được thay thế bởi chuỗi các phát biểu mà ngôn ngữ lập trình cổ điển có. 4. Mở rộng ngôn ngữ (language extension). Bộ tiền xử lý tăng khả năng cho ngôn ngữ bằng một số các macro nội tại của nó. Thí dụ ngôn ngữ Equel là ngôn ngữ hỏi đáp với cơ sở dữ liệu được nhúng vào ngôn ngữ C. Các phát biểu được bắt đầu bằng hai dấu # # ở trong C được bộ tiền xử lý, xử lý, là các phát biểu truy xuất cơ sở dữ liệu, không liên quan đến C, được dịch thành các phát biểu gọi thủ tục, sẽ gọi các trình con đặc nhiệm trong mã máy để thực hiện việc truy xuất cơ sở dữ liệu. Bây giờ ta sẽ nói kỹ hơn về bộ xử lý macro. Bộ xử lý này thường làm việc với hai loại phát biểu: định nghĩa macro và sử dụng macro. Định nghĩa macro bao gồm: từ khoá define hoặc macro, tiếp theo là tên macro. Theo sau là thân (body) của macro. Chẳng hạn, \define {}. Thông thường bộ xử lý macro cho phép các thông số hình thức (formal parameter) trong định nghĩa, chúng là các ký hiệu sẽ bị thay thế bởi các trị (chuỗi các ký tự) sau này khi macro được dùng. Phát biểu dùng macro bao gồm: tên macro và các thông số thực (actual parameter), là trị của các thông số hình thức trong thân của macro. Thí dụ 9: Hệ thóng đánh máy typesetting có phương tiện macro với phát biểu định nghĩa macro như sau: \define {} : tên macro : danh sách thông số hình thức : thân macro Macro định nghĩa ve sự trích dẫn của tạp chí ACM như sau: \define\JACM #1; #2; #3 {{\S1 J.ACM}{\bf #1}: #2, pp. #3} Tên macro là \JACM. Các thông số hình thức là #1, #2, #3 được ngăn cách nhau bởi dấu ‘;’ và được kết thúc bằng dấu ‘.’. Khi dùng macro, người sử dụng sẽ viết như sau: \JACM 17; 4; 715 – 728 sẽ được hiểu như sau: J.ACM 17: 4, pp. 715 – 728. 5.3.2. Trình biên dịch hợp ngữ: Một số trình biên dịch cho sản phẩm ở đầu ra là mã hợp ngữ, chuỗi mã hợp ngữ này sẽ được đưa sang trình biên dịch hợp ngữ xử lý tiếp. Một số trình biên dịch khác thực hiện luôn công việc của assembler, nghĩa là nó dịch ra luôn mã máy khả định vị (relocatable machine code), mã máy sẽ được chuyển trực tiếp đến bộ phận “loader/link editor. 88 Mã hợp ngữ là phiên bản gợi nhớ của mã máy, trong đó các tên sẽ được dùng thay thế cho các mã nhị phân của các tác vụ và tên cũng được đại diện cho các địa chỉ của vị trí nhớ. Chẳng hạn, chuỗi chỉ thị trong mã hợp ngữ của phát biểu gán b := a+2. mov a, R1 add #2, R1 (4) mov R1, b Ba chỉ thị thực hiện việc chuyển nội dung ở địa chỉ a vào thanh ghi R1, sau đó cộng hằng số 2 với nội dung của R1 và kết quả được giữ lại trong thanh ghi R1, cuối cùng là chuyển nội dung của R1 vào địa chỉ b. Sau khi thực hiện ba chỉ thị thì máy thực sự đã thực hiện phát biểu gán b:=a+2. Thông thường hợp ngữ cũng có các phương tiện macro và bộ tiền xử lý macro. 5.3.3. Trình biên dịch hợp ngữ hai chuyến (two pass assembler): Trình biên dịch hợp ngữ đơn giản nhất là biên dịch hai chuyến trên dữ liệu nhập vào. Chuyến ở đây được coi là lần đọc tập tin nhập trọn vẹn. Ở chuyến đầu, toàn bộ danh biểu, đại diện cho vị trí nhớ sẽ được nhặt ra, cất vào bảng danh biểu. bằng tên) của tác vụ sang chuỗi mã máy – mã nh diện cho vị trí nhớ sẽ được thay thế bằng địa chỉ bảng danh biểu. a 0 Theo bảng bên, ta giả sử địa chỉ được đánh cho từng từ (một từ là 4 byte). a là danh biểu đại diện cho địa chỉ bắt đầu ở byte 0. b ở thứ 4. Ở chuyến thứ hai, trình biên dịch hợp ngữ sẽ rà lại tập tin nhập một lần nữa. Lần này n Thí dụ 10: Đoạn chỉ thị (4) được dịch sang mã má 0001 010000000000* 0011 011000000010* (5) 0100 010000000100* 4 bit đầu là mã tác vụ 0001, 0011, 0100 là theo 01 ở ba chỉ thị là mã của thanh ghi 1. 2 bit tiế bit theo sau là địa chỉ hay toán hạng. Hai bit này đ và mode trực tiếp – toán hạng nếu là 10. Vì vậy ngược lại ở chỉ thị 2, 00000010 là toán hạng, hằng Đầu ra chuyến thứ hai của trình biên dịch nghĩa là chương trình trong dạng này có thể được nào. Như vậy địa chỉ tương đối trong bảng danh b chỉ tuyệt đối, bằng cách lấy L cộng với địa chỉ tư 89b 4 ó sẽ dịch mã gợi nhớ (được đặtDanh biểu Địa chỉ tương đối ị phân và phần tên danh biểu đại tương đối của danh biểu đó trong y là: mã load, add, store. Hai bit tiếp p theo là mã thông báo cho biết 8 ược gọi là mode địa chỉ nếu là 00 8 bit của chỉ thị 1 và 3 là địa chỉ, nguyên có trị 2. hợp ngữ là mã máy khả định vị, chứa vào bộ nhớ ở bất kỳ vị trí L iểu sẽ được tính lại, trở thành địa ơng đối, việc này được thực hiện cho tất cả các danh biểu trong bảng danh biểu. Quay lại (5), ta thấy ở chỉ thị 1 và 3 thì 8 bit sau cùng là địa chỉ tương đối của danh biểu a, b. Giả sử L=00001111, địa chỉ tuyệt đối của a, b là 00001111, 00010011. Ba chỉ thị (5) được viết lại dưới dạng mã máy tuyệt đối: 0001010000001111 0011011000000010 (6) 0010010000010011 5.3.4. Bộ cất liên kết soạn thảo (loader/link editor): Loader là chương trình, thực hiện hai nhiệm vụ sau: cất và soạn thảo liên kết. Quá trình cất bao gồm lấy mã máy khả định vị tính lại địa chỉ thành địa chỉ tuyệt đối như ở thí dụ trên. Sau đó ta đem cất tất cả chỉ thị với các địa chỉ tuyệt đối của danh biểu và dữ liệu vào trong bộ nhớ tại vị trí tương ứng như ở (6). Link editor cho phép ta tạo một chương trình duy nhất từ nhiều tập tin ở dạng mã máy khả định vị của những lần biên dịch riêng biệt và từ những tập tin thư viện, do hệ thống cung cấp. Sự liên kết này tạo điều kiện thuận lợi cho bất kỳ chương trình nào cần tới chúng khi thực thi. Nếu có một số tập tin được chương trình khác tham chiếu, chúng sẽ được tham chiếu ngoài (external reference). Trong đó mã của tập tin này có thể tham chiếu đến một vị trí nhớ trong tập tin khác. Có nghĩa là vị trí nhớ chứa dữ liệu được khai báo trong một tập tin lại có thể được truy xuất ở tập tin khác. Hoặc thủ tục được khai báo trong tập tin này lại được gọi trong tập tin khác. Chương trình nguồn viết tắt Bộ tiền xử lý Hệ thống Trình biên dịch Chương trình nguồn xử lý ngôn ngữ Trình biên dịch hợp ngữ Chương trình đối tượng trong mã hợp ngữ Bộ cất/liên kết-soạn thảo Chương trình trong mã máy với địa chỉ tuyệt đối Thư viện hệ thống, các tập tin đối tượng khả định vị địa chỉ Chương trình trong mã máy khả định vị 90 Mã khả định vị phải lưu giữ thông tin trong bảng danh biểu cho danh biểu và tên các thủ tục. Vì ta không thể biết được toàn bộ chương trình trong dạng mã khả định vị sẽ được chứa ở đâu trong bộ nhớ trong khi nó còn ở bộ nhớ ngoài, do đó toàn bộ bảng danh biểu phải được lưu giũ đầy đủ như là một phần của chương trình trong mã khả định vị. Ở bảng trong 5.3.3, ta thấy: khi có một tập tin được thực thi, nó tham chiếu đến b thì vị trí nhớ của b + địa chỉ bắt đầu vùng dữ liệu của tập tin (6), được cất trong bộ nhớ trong. 5.4. NHÓM CÁC GIAI ĐOẠN CỦA TRÌNH BIÊN DỊCH. Như trong phần trước ta đã thấy tổ chức luận lý của trình biên dịch gồm nhiều giai đoạn. Song thực tế một số các giai đoạn thường được gộp lại thành một giai đoạn lớn hơn. 5.4.1. Giai đoạn trước và giai đoạn sau (front end and back end): Thông thường các giai đoạn được nhóm lại trong hai giai đoạn bao trùm hơn là giai đoạn trước (front end) và giai đoạn sau (back end). Giai đoạn trước bao gồm các giai đoạn, hoặc các phần của các giai đoạn mà chúng chỉ phụ thuộc vào ngôn ngữ nguồn mà hầu như không phụ thuộc vào máy đích. Giai đoạn đầu này bao gồm phân tích từ vựng, phân tích cú pháp, tạo bảng danh biểu, phân tích ngữ nghĩa, thông báo lỗi và sinh mã trung gian. Phần lớn tối ưu mã trung gian cũng nằm trong giai đoạn đầu. Giai đoạn sau bao gồm những phần phụ thuộc vào máy đích, mà không (về tổng quát) phụ thuộc vào ngôn ngữ nguồn. Giai đoạn này bao gồm giai đoạn sinh mã đối tượng, tối ưu mã đối tượng và tất nhiên nó cần các tác vụ của thông báo lỗi và bảng danh biểu. Với ý niệm như vậy có thể xuất hiện một thủ tục đặc biệt, sẽ lấy giai đoạn đầu của trình biên dịch kết nối với các phần sau để tạo ra một trình biên dịch cho cùng một ngôn ngữ nguồn trên các máy khác nhau. Hoặc ngược lại, có thể các trình biên dịch cho nhiều ngôn ngữ nguồn khác nhau, có chung một ngôn ngữ trung gian và dùng chung giai đoạn cuối, sẽ cho ta nhiều trình biên dịch trên một máy. 5.4.2. Các chuyến: Thông thường một số giai đoạn có thể hiện thực trong một chuyến. Chẳng hạn, phân tích từ vựng, phân tích cú pháp, phân tích ngữ nghĩa và sinh mã trung gian có thể được gom lại, hiện thực trong một chuyến. Nếu như vậy thì chuỗi token được nhận dạng sẽ được dịch thẳng sang mã trung gian. Nói chi tiết hơn, ta sẽ thấy vai trò bộ phân tích cú pháp là bao trùm, nó trông coi toàn bộ hoạt động của chuyến. Nó có nhiệm vụ phải phát hiện cấu trúc văn phạm của các token đưa đến cho nó. Nó lại phải biết lúc nào cần lấy tiếp token và nó sẽ gọi bộ phân tích từ vựng nhận dạng token kế tiếp. Khi đã phát hiện xong một cấu trúc văn phạm, bộ 91 phân tích cú pháp sẽ gọi bộ sinh mã trung gian, để thực hiện phân tích ngữ nghĩa và tạo mã trung gian. 5.4.3. Thu giảm số lượng các chuyến: Nếu một quá trình dịch được chia thành nhiều chuyến, nó sẽ làm tăng thời gian để đọc và ghi lên bộ nhớ ngoài mã trung gian. Ngược lại, nếu ta gom một số giai đoạn thành một chuyến thì buộc phải giữ toàn bộ chương trình trong bộ nhớ. Bởi vì giai đoạn đoạn này sẽ cần những thông tin theo thứ tự khác với thứ tự mà giai đoạn trước tạo ra, như vậy vấn đề bộ nhớ không phải là đơn giản. Việc thực hiện gom một số giai đoạn trong một chuyến phải giải quyết được một số vấn đề sau. Việc giao tiếp giữa bộ phân tích từ vựng và phân tích cú pháp có thể được giới hạn ở một token vì khi nào bộ phân tích cú pháp cần tới một token sẽ gọi bộ phân tích từ vựng cung cấp. Nhưng thật khó để thực hiện việc sinh mã đối tượng khi toàn bộ mã trung gian của chương trình nguồn chưa được tạo xong. Chẳng hạn, trong PL/I, Algol 68 cho phép dùng biến trước khi nó được khai báo, như vậy ta không thể tạo mã đối tượng cho một cấu trúc mã mà ta chưa biết loại của biến, được xuất hiện trong nó. Rõ ràng trong trường hợp này phải có sự phân tích ngữ nghĩa, kiểm tra kiểu dữ liệu tại cấu trúc cụ thể để quyết định xem biến đó thuộc kiểu nào, khi đã kết luận được thì bộ sinh mã trung gian mới sinh mã được. Cũng tương tự trong trường hợp phát biểu goto tham khảo trước, các phát biểu goto L có thứ tự đứng trước phát biểu có nhãn L. Khi dịch ra mã đối tượng, bộ sinh mã sẽ sinh mã cho tác vụ goto còn địa chỉ có tên L thì chưa được thay thế vì tại thời điểm đó, nó chưa nhìn thấy chỉ thị có nhãn L, nên không biết chỉ thị đó nằm ở địa chỉ nào. Bộ sinh mã sẽ tạo ra một danh sách liên kết, ghi nhớ địa chỉ của các chỉ thị goto L. Khi gặp chỉ thị có nhãn L, bộ sinh mã đã xác định được địa chỉ có tên là L, nó sẽ lần theo danh sách liên kết để điền vào các chỉ thị goto địa chỉ của L. 92 PHỤ LỤC: CÁC LỚP P VÀ NP VÀ LỚP CÁC BÀI TOÁN NP-ĐẦY ĐỦ Có những bài toán thực tế mà cho đến nay vẫn chưa xây dựng được thuật toán hiệu quả để giải (đó là thuật toán có độ phức tạp tính toán là đa thức) và chứng minh được mức độ khó thực chất của nó. Trong số các bài toán như vậy, có thể kể ra các bài toán nổi tiếng sau: Bài toán người du lịch, Bài toán chu trình Hamilton, Bài toán tô màu đồ thị, Bài toán tìm đường đi đơn dài nhất của đồ thị. Ta có thể quy lỗi cho việc thiết kế và phân tích thuật toán hay lý thuyết độ phức tạp hay không? Liệu trên thực tế có thuật toán hiệu quả để giải quyết các bài toán này không? Trong phần này, ta sẽ có một kết quả nổi tiếng: mỗi thuật toán hiệu quả để giải một trong số các bài toán vừa kể trên sẽ cũng cho ta thuật toán hiệu quả để giải tất cả các bài toán còn lại. Ta chưa biết những bài toán này là dễ hay khó giải, nhưng ta biết rằng tất cả chúng có độ phức tạp như nhau. Ý nghĩa thực tế quan trọng của các bài toán này là đảm bảo rằng mỗi một bài toán này là đối tượng của những cố gắng tìm thuật toán hiệu quả để giải. 1. LỚP P VÀ LỚP NP. 1.1. Định nghĩa: Cho M là một máy Turing. Hàm T(n) được gọi là độ phức tạp tính toán của M nếu với mọi xâu vào ω có độ dài n thì đều tồn tại một dãy hình trạng có nhiều nhất là T(n) bước đoán nhận ω (ở đây T(n) là một số nguyên dương). Nếu có một xâu nào đó có độ dài n mà máy Turing không dừng thì đối với n đó, T(n) không xác định. 1.2. Định nghĩa: Lớp P là lớp các ngôn ngữ được đoán nhận bởi máy Turing đơn định và độ phức tạp tính toán là đa thức. Có thể phát biểu một cách khác là: một bài toán được coi là thuộc lớp P nếu tồn tại một thuật toán đa thức để giải nó. Người ta nói rằng những bài toán thuộc lớp P là dễ. 1.3. Chú ý: Theo quan điểm toán học, lớp P là rất tự nhiên. Điều này thấy được từ việc nó là bất biến cao đối với mô hình tính toán được dùng. Chẳng hạn, các máy Turing M1 với nhiều băng là nhanh hơn các máy Turing thông thường, tức là độ phức tạp tính toán của chúng nhận các giá trị nhỏ hơn. Tuy nhiên, nếu độ phức tạp tính toán của một máy Turing M1 như vậy bị chặn trên bởi một đa thức T1(n), ta có thể xây dựng một máy Turing thông thường M với giới hạn thời gian đa thức T(n) 93 đoán nhận chính ngôn ngữ như M1. (Nói chung, T(n) nhận giá trị lớn hơn T1(n) nhưng vẫn là đa thức). Tương tự, mỗi ngôn ngữ là trong giới hạn đa thức đối với một mô hình máy Turing chuẩn mực bất kỳ hay đối với một mô hình tính toán hợp lý bất kỳ đều thuộc vào lớp P được định nghĩa như ở trên đối với các máy Turing thông thường. Lớp P cũng có tầm quan trọng quyết định vì các ngôn ngữ nằm ngoài P có thể xem là không thể tính được. Trên thực tế ta nói rằng một ngôn ngữ đệ quy là bất trị nếu nó không thuộc P. Rõ ràng rằng các ngôn ngữ nằm ngoài P là bất trị theo quan điểm thực hành. Ta cũng có thể nói như vậy đối với các ngôn ngữ trong P có cận là một đa thức khổng lồ. Tuy nhiên, việc vạch ra một ranh giới giữa tính bất trị và tính không bất trị bên trong P là không tự nhiên lắm. Một định nghĩa như vậy sẽ thay đổi theo thời gian: sự phát triển kỳ diệu trong lĩnh vực máy tính có thể làm thay đổi ranh giới này. Mặt khác, lớp P cho ta một cách đặc trưng rất tự nhiên cho tính không bất trị. Thí dụ 1: Bài toán tìm đường đi ngắn nhất giữa hai thành phố A và B là bài toán dễ vì độ phức tạp của thuật toán để giải nó là O(n2) (tức là một thuật toán đa thức). Ta xét dưới đây các bài toán thuộc lớp sẽ được gọi là lớp NP. Theo định nghĩa trên, ta nêu ra thí dụ về bài toán “khó”. Giả sử người ta đòi hỏi xác định tất cả các con đường nối đỉnh S với đỉnh T trong một mạng nào đó và có độ dài nhỏ hơn (1+ε) lần so với độ dài của đường đi ngắn nhất. Người ta có thể không có khả năng lập nên danh mục này trong thời gian đa thức (cách nói này có ý nghĩa tương tự với số các phép toán) vì một nguyên nhân đơn giản là danh mục này chứa một số các phần tử không đa thức (nghĩa là nó không bị chặn bởi một đa thức theo số các dữ liệu). 1.4. Định nghĩa: Một bài toán được gọi là “nhận biết” nếu đó là bài toán mà các kết quả chỉ có thể lập một trong hai giá trị tại ĐÚNG hay SAI. Thí dụ 2: 1) Bài toán về việc tìm phân bố phù hợp. Cho tập hợp X={x1, x2, …, xn} gồm các biến Boole và một biểu thức Boole đối với các số hạng của các biến này: E=C1∧C2∧…∧Cm, trong đó Ci (i=1,…, m) là biểu thức Ci=uj1∨uj2∨…∨ujk(i), trong đó mỗi ujq là một trong các biến của X. Bài toán đặt ra là thử tìm xem có một phân bố các biến xk (k=1,…,n) bằng 0 hay 1 sao cho E=1. Đối với E= 321321 )()( xxxxxx ∧∨∧∨∨ có câu trả lời là ĐÚNG khi lấy x1=0 hay 1, x2=1, x3=1. Tuy nhiên, câu trả lời là SAI trong trường hợp này đối với E= )()()( 32321321 xxxxxxxx ∨∧∧∨∧∨∨ . 2) Bài toán về chu trình Hamilton. Vấn đề đặt ra là xác định xem trong một đồ thị G đã cho có một chu trình sơ cấp đi qua tất cả các đỉnh hay không? 94 Nghiệm của bài toán nhận biết chỉ là ĐÚNG hoặc SAI. Người ta không đòi hỏi gì hơn. Điều này phân biệt một cách cơ bản các bài toán nhận biết với các bài toán tồn tại cũng như đối với bài toán về sự tìm phân bố phù hợp, nếu câu trả lời là ĐÚNG, người ta không đòi hỏi cho một phân bố các biến của X cho E giá trị 1. Đối với bài toán chu trình Hamilton, người ta không đòi hỏi diễn tả chu trình. 1.5. Định nghĩa: Cho bài toán tối ưu hoá tổ hợp (f(s)) (tương ứng (f(s))) Ss∈min Ss∈ max và một số a. Người ta định nghĩa “bài toán nhận biết liên hợp” là bài toán: liệu có tồn tại s∈S sao cho f(s)≤a (tương ứng f(s)≥a). Thí dụ 3: 1) Cho một tập n thành phố, các khoảng cách giữa các thành phố và một số a. Bài toán với nội dung là xác định xem có tồn tại một vòng đi với chi phí nhỏ hơn hoặc bằng a là bài toán nhận biết liên hợp của bài toán người du lịch. 2) Cho một ma trận A và vectơ b với các hệ số nguyên. Bài toán có nội dung là xác định xem có tồn tại vectơ x có các thành phần nguyên sao cho Ax≤b là một bài toán nhận biết. Nếu đặt ⎟⎟⎠ ⎞⎜⎜⎝ ⎛= A C A , ⎟⎟⎠ ⎞⎜⎜⎝ ⎛= b a b , ta có thể coi bài toán nhận biết là liên hợp với bài toán quy hoạch tuyến tính nguyên: Cx=z(min) ⎪⎩ ⎪⎨⎧ =∈ ≤ .,1, njNx bAx j 1.6. Định lý: Nếu bài toán nhận biết liên hợp của một bài toán tối ưu hoá tổ hợp đã cho là “khó” thì bài toán tối ưu hoá tổ hợp cũng là “khó”. Định lý 1.6 chỉ ra rằng bài toán tối ưu hoá tổ hợp ít nhất là “khó” như bài toán nhận biết liên hợp. Trong thực tế người ta luôn luôn có thể chứng minh rằng bài toán nhận biết (chẳng hạn bài toán người du lịch) không phải là “dễ hơn” bài toán tối ưu hoá tổ hợp mà nó liên hợp. 1.7. Nhận xét: Ký hiệu NP đặc trưng cho lớp các bài toán mà ta sẽ nghiên cứu bây giờ trở nên như là “lường gạt”. Vấn đề là nó không phải thuộc các bài toán “không phải là đa thức” như người ta tưởng. Giả sử rằng ta biết câu trả lời của một bài toán nhận biết là ĐÚNG. Nếu ta có thể chia sẻ sự tin chắc của ta cho một người “siêu quan sát” bằng thời gian đa thức thì bài toán thuộc lớp NP, ngay cả khi ta không biết tìm bằng thời gian đa thức một nghiệm s mà đối với nó câu trả lời là ĐÚNG. Người ta chỉ đòi hỏi rằng nếu nghiệm s được đề xuất thì người ta có thể thử lại bằng thời gian đa thức rằng câu trả lời tương ứng là ĐÚNG. 95 Các bài toán về sự tìm phân bố phù hợp, về chu trình Hamilton, về nhận biết liên hợp với bài toán người du lịch và bài toán nhận biết liên hợp của quy hoạch tuyến tính nguyên là các bài toán thuộc lớp NP. Bây giờ ta xét các máy Turing không đơn định: khi đọc mỗi ký hiệu bất kỳ ở một trạng thái bất kỳ, máy được phép có một số khả năng hành động. Còn về các yếu tố khác, một máy Turing không đơn định được định nghĩa như một máy đơn định. Một từ ω được đoán nhận nếu nó sinh ra một tính toán đoán nhận được, độc lập với việc nó cũng có thể sinh ra các tính toán khác dẫn đến thất bại. Như vậy, khi quan hệ với các máy không đơn định, ta không quan tâm đến mọi con đường dẫn đến thất bại nếu có một con đường có thể có dẫn đến thành công. Thời gian cần thiết để máy Turring không đơn định M đoán nhận một từ ω∈T(M) được định nghĩa bằng số bước trong tính toán ngắn nhất của M dùng để đoán nhận ω. 1.8. Định nghĩa: Lớp NP là lớp các ngôn ngữ được đoán nhận bởi các máy Turing không đơn định trong giới hạn đa thức. 1.9. Chú ý: Các bài toán trong lớp P là trị liệu được, trong khi đó, các bài toán trong lớp NP có tính chất là việc kiểm chứng xem một phỏng đoán tốt không đối với việc giải bài toán có là đúng đắn không là trị liệu được. Một máy Turing không đơn định có thể được hình dung như một thiết bị kiểm chứng xem một phỏng đoán có đúng hay không: nó tiến hành một (hay một số) phỏng đoán ở từng bước trong suốt quá trình tính toán và chung cuộc là việc đoán nhận chỉ trong trường hợp (các) phỏng đoán này là đúng đắn. Như vậy, trong thực tế một giới hạn thời gian đối với một máy Turing không đơn định là một giới hạn thời gian để kiểm chứng xem một phỏng đoán đối với lời giải có là đúng đắn không. Dễ thấy lớp P là một lớp con của lớp NP. Tuy nhiên, ta không biết liệu bao hàm này có là thực sự hay không. Vấn đề “P có bằng NP hay không” có thể xem là vấn đề tồn tại nổi tiếng nhất trong lý thuyết tính toán. Vấn đề này có ý nghĩa vì nhiều bài toán quan trọng trong thực tế được biết là thuộc NP, trong khi đó ta không biết nó có thuộc P hay không. Thực ra, về mặt thời gian, mọi thuật toán đơn định được biết đối với các bài toán này đều là mũ. Như vậy, một chứng minh cho P=NP sẽ làm cho mọi bài toán này trị liệu được. Các máy Turing không đơn định và việc đoán chừng vốn không được dự định để mô hình hoá việc tính toán. Tính không đơn định chỉ là một khái niệm bổ trợ và như ta sẽ thấy, nó rất tiện lợi. Thực vậy, nếu ta muốn giải quyết vấn đề có hay không đẳng thức P=NP, các định nghĩa và kết quả sau này chứng tỏ rằng chỉ cần xét một ngôn ngữ đặc biệt (có thể là một ngôn ngữ ta ưa thích!) và xác định 96 xem nó có thuộc P hay không. Có một số lớn và rất đa dạng các ngôn ngữ mà ta sẽ gọi là các ngôn ngữ NP-đầy đủ nhận được thực tế từ mọi lĩnh vực của toán học. 1.10. Định nghĩa: Ngôn ngữ L1⊂Σ1* được gọi là dẫn được trong thời gian đa thức về ngôn ngữ L2⊂Σ2*, ký hiệu L1 ≤P L2, nếu có một hàm xác định bởi máy Turing đơn định trong thời gian đa thức f: Σ1* ⎯→⎯ Σ2* thoả mãn: ∀ω∈Σ1*, ω∈L1 ⇔ f(ω)∈L2. Ta nhận thấy rằng máy Turing M được đưa vào trong định nghĩa trên phải dừng với mọi dữ liệu vào, đó là một hệ quả của việc M là đơn định và trong thời gian đa thức. Kết quả tiếp theo là một hệ quả trực tiếp của định nghĩa. 1.11. Mệnh đề: Nếu L1 ≤P L2 và L2∈P thì L1∈P. 2. LỚP NP-ĐẦY ĐỦ. Đối với phần lớn các bài toán thuộc lớp NP, người ta không nói được là chúng có thể giải được hay không bằng một thuật toán đa thức. Chỉ biết rằng người ta chưa tìm được một thuật toán đa thức để giải chúng. Để chứng minh P=NP, ta phải chứng tỏ rằng trong lớp NP tất cả các bài toán có thể giải với thời gian đa thức bằng các thuật toán đơn định.. Để chứng minh P≠NP, ta phải chỉ ra một bài toán trong NP mà không thể giải được một cách tiền định với thời gian đa thức. Cách giải quyết hiện nay là xây dựng lớp các bài toán tương đương. 2.1. Định nghĩa: Một ngôn ngữ L được gọi là NP-khó nếu với mọi ngôn ngữ L’ trong NP, ta có L’ ≤P L. Ngôn ngữ L được gọi là NP-đầy đủ nếu nó là NP-khó và L∈NP. 2.2. Chú ý: Các ngôn ngữ NP-đầy đủ có thể hình dung như đại diện cho các bài toán khó nhất trong NP. Hơn nữa, để giải quyết vấn đề có P=NP không, chỉ cần quyết định xem một ngôn ngữ NP-đầy đủ L nào đó có thuộc P hay không. Thật vậy, xét một ngôn ngữ L như vậy. Nếu L không thuộc P thì rõ ràng P≠NP. Nếu L thuộc P thì định nghĩa của tính NP-đầy đủ và Mệnh đề 1.11 chứng tỏ rằng mỗi ngôn ngữ thuộc NP cũng thuộc P. Nhưng điều đó có nghĩa là P=NP. Ta có thể xây dựng cho mỗi bài toán trong lớp NP một thuật toán làm việc trong thời gian đa thức miễn là ta biết một thuật toán (đơn định) trong giới hạn thời gian đa thức đối với một bài toán NP-đầy đủ nào đó. (Hiện thời ta nói về các bài toán thay cho các ngôn ngữ để nhắc nhở rằng có thể thay đổi qua lại giữa các khái niệm này). Như vậy, một khi chúng ta có được một thuật toán trong giới hạn thời gian đa thức cho một trong số rất nhiều bài toán NP-đầy đủ, ta sẽ có được thuật toán trong giới hạn thời gian đa thức cho mỗi bài toán trong lớp NP! Do những nỗ lực cực kỳ lớn dành cho dự định cải tiến các thuật toán đã được biết cho một số 97 trong các bài toán như vậy (do tầm quan trọng thực tế lớn lao của chúng) và do chưa một nỗ lực nào như vậy dẫn đến thành công, bây giờ nói chung người ta tin rằng P≠NP. Mệnh đề sau đây là một hệ quả trực tiếp của tính bắc cầu của quan hệ ≤P. 2.3. Mệnh đề: Nếu L1 là NP-đầy đủ và L2 là một ngôn ngữ trong lớp NP thoả mãn L1 ≤P L2 thì ngôn ngữ L2 cũng là NP-đầy đủ. Thí dụ 4: Xét bảng chữ: Σ = {1, 2, ∨, ∧, , (, )}. Một từ ω trên bảng chữ Σ được gọi là một công thức được thiết lập đúng của phép tính mệnh đề, viết tắt là wffpc, nếu hoặc (1) hoặc (2) đúng. (1) ω là một từ khác rỗng trên bảng chữ {1, 2}. (2) Có các wffpc u và v sao cho: ω=(u ∨ v) hay ω=(u ∧ v) hay ω=u . Về mặt trực giác, ∨, ∧ và chỉ phép tuyển, phép hội và phép phủ định. Trong các wffpc, ta có thể có nhiều không hạn chế các biến xi mà i là một số nguyên theo cách viết 2-adic. Chẳng han, thay vì x9 thì ta viết 121. Điều kiện (1) nói rằng mỗi biến đơn lẻ là một wffpc. Một cách hình thức, mọi từ con α∈{1, 2}+ của một wffpc ω thoả mãn các điều kiện: ω=ω1αω2, ω1∉Σ*{1, 2}, ω2∉{1, 2}Σ* được gọi là một biến. Giả sử α1, …, αn là tất cả các biến có mặt trong một wffpc ω. Một ánh xạ T từ tập {α1, …, αn} đến tập {0, 1} được gọi là một phép gán giá trị chân lý cho ω. Giá trị chân lý của một biến αi bằng T(αi). Giá trị chân lý của (u ∨ v) (tương ứng của (u ∧ v)) bằng max(u1, v1) (tương ứng min(u1, v1)), trong đó u1 và v1 tương ứng là các giá trị chân lý của u và v. Giá trị chân lý của u bằng 1−u1. Một wffpc ω được gọi là thoả được nếu nó nhận giá trị chân lý 1 đối với một cách gán giá trị chân lý T nào đó. Ta ký hiệu ngôn ngữ trên Σ gồm mọi wffpc thoả được là SAT. Về mặt trực giác, 1 và 0 ký hiệu tương ứng các giá trị chân lý đúng và sai.. Một wffpc là thoả được nếu nó không là đồng nhất sai theo kỹ thuật bảng chân lý quen thuộc. Tất nhiên, trong mỗi cách gán giá trị chân lý, mọi xuất hiện của mỗi biến cá biệt αi nhận cùng một giá trị chân lý. Sau đây, các quy tắc nghiêm ngặt về định nghĩa của một wffpc được giảm nhẹ đôi chút. Ta dùng các chữ thường ở cuối bảng chữ cái để ký hiệu các biến. Như vậy, một biến cá biệt có thể được ký hiệu là x9 thay cho ký hiệu 121 đã chỉ ra trong định nghĩa. Các dấu ngoặc không cần thiết được bỏ đi. Quy ước này cũng áp 98 dụng đối với các dấu ngoặc không cần thiết do tính kết hợp của ∧ và ∨. (Ta chỉ quan tâm đến các giá trị chân lý và rõ ràng rằng các hàm min và max là kết hợp). Xét hai wffpc sau đây: 3212121 )()()( xxxxxxx ∧∨∧∨∧∨ (1) 33132321 )()()( xxxxxxxx ∧∨∧∨∧∨∨ (2) Cả hai (1) và (2) đều là hội của wffpc mà mỗi một trong số chúng là tuyển của các ký hiệu chữ, trong đó các biến và các phủ định của chúng được gọi là các ký hiệu chữ. Ta nói rằng các wffpc thuộc loại này là ở dạng chuẩn hội. Hơn nữa, nếu mỗi tuyển chứa nhiều nhất ba (tương ứng hai) ký hiệu chữ, ta nói rằng wffpc này là ở dạng chuẩn 3-hội (tương ứng 2-hội). Như vậy, (2) là ở dạng chuẩn 3-hội và (1) ở dạng chuẩn 2-hội (đồng thời cũng ở dạng chuẩn 3-hội). Ta ký hiệu ngôn ngữ trên Σ gồm mọi wffpc thoả được ở dạng chuẩn hội là CONSAT. Các ký hiệu 3-CONSAT và 2-CONSAT được định nghĩa tương tự. wffpc (1) thuộc 2-CONSAT nhưng wffpc (2) không thuộc 3-CONSAT vì tuyệt nhiên nó không là thoả được. Ta có thể thấy điều đó nhờ lý luận sau. Câu cuối cùng của (2) buộc ta phải gán trị 0 cho x3. Do đó, các câu thứ hai và thứ ba buộc ta phải gán trị 1 và 0 tương ứng cho x2 và x1. Nhưng với cách gán trị này, câu thứ nhất nhận giá trị 0. Rõ ràng tính thoả được là một tính chất có thể quyết định được. Ta chỉ cần kiểm tra qua tất cả 2n cách gán trị chân lý có thể có đối với n biến. (Thực ra điều này cũng chẳng khác gì so với kỹ thuật bảng chân lý quen thuộc). Một cách kiểm tra vét cạn như thế dùng một lượng thời gian mũ (theo số biến hay độ dài của wffpc cho trước). Bây giờ ta mô tả một cách ngắn gọn một thuật toán để kiểm tra tính thoả được dựa trên việc rút gọn số biến. Ta giả thiết rằng dữ liệu vào được cho dưới dạng chuẩn hội. Thuật toán này bộc lộ sự khác nhau đáng kể giữa các dạng chuẩn 2-hội và 3-hội. Giả sử rằng α là một wffpc ở dạng chuẩn hội. Như vậy α = α1 ∧ α2 ∧…∧ αk, trong đó mỗi αi là một tuyển của các ký hiệu chữ. Ta gọi các tuyển αi là các mệnh đề. Bước 1: Bảo đảm cho mỗi biến xuất hiện (hoặc bị phủ định hoặc không) nhiều nhất một lần trong mỗi mệnh đề. Điều này được thực hiện bằng cách biến đổi α như sau. Mỗi mệnh đề chứa cả x và x với một biến x nào đó bị bỏ đi khỏi α. Nếu x (tương ứng x ) xuất hiện một số lần trong một mệnh đề nào đó, nhưng xuất hiện này được thay bằng một xuất hiện duy nhất của x (tương ứng x ). Nếu tất cả bị bỏ đi, α là thoả được. (Thực tế là nó đồng dạng đúng). Trái lại, giả sử α’ là wffpc thu được. 99 Bước 2: Thay α’ bằng một wffpc α’’ không chứa một mệnh đề nào chỉ có một ký hiệu chữ (và cũng thoả mãn điều kiện được đòi hỏi đối với α’ sau Bước 1). Thực vậy, nếu x (tương ứng x ) xuất hiện đơn độc trong một mệnh đề nào đó, ta bỏ đi mọi mệnh đề chứa x (tương ứng x ) và tiếp đó loại bỏ x (tương ứng x) khỏi mọi mệnh đề mà trong đó nó xuất hiện cùng với một biến khác nào đó; nếu x (tương ứng x) xuất hiện một mình trong một mệnh đề khác nào đó, ta kết luận rằng α không là thoả được. Lặp lại thủ tục này cho tới khi thu được α’’ như mô tả ở trên. Bước 3: Nếu không có biến nào xuất hiện trong α’’ vừa bị phủ định và vừa không bị phủ định, ta kết luận rằng α’’ là thoả được. Nếu trái lại, ta chọn một biến x nào đó mà cả x và x đều xuất hiện trong α’’. Ta tìm mọi mệnh đề ),(),...,(),(),...,( 11 nm xxxx γγββ ∨∨∨∨ trong đó x hay x xuất hiện. Giả sử δ là hội của mọi mệnh đề khác (nếu còn). Khi đó α’’ là thoả được nếu wffpc δγγββ ∧∧∧∨∧∧ ))...()...(( 11 nm là thoả được. Ta nhận thấy rằng mỗi một trong số các β và γ chứa ít nhất một ký hiệu chữ và chứa đúng một ký hiệu chữ nếu α nguyên bản là ở dạng chuẩn 2-hội. Nếu một trong số các β hay γ chứa hơn một ký hiệu chữ ta thay α’’ bằng hai wffpc δββα ∧∧∧= m...1 và ,...1 δγγα ∧∧∧= n bảo đảm cả α lẫn α đều không chứa cùng một mệnh đề hai lần (bằng cách bỏ đi những xuất hiện không cần thiết) và quay về Bước 1. wffpc ban đầu α là thoả được nếu α hay α là thoả được. Nếu mọi β và γ chứa đúng một ký hiệu chữ, ta thay α’’ bằng wffpc ,)(...)(...)(''' 111 δγβγβγβα ∧∨∧∧∨∧∧∨= nmn loại bỏ những xuất hiện bị lặp lại của cùng một mệnh đề và quay về Bước 1. α ban đầu là thoả được nếu α’’’ là thoả được. Đến đây ta kết thúc việc mô tả thuật toán. Chúng ta có thể dễ dàng kiểm nghiệm rằng phương pháp này có hiệu lực. Một số giải thích đã được cho ở trên. Điều cốt yếu là số lượng biến thực sự giảm trước mỗi lần quay về Bước 1. Xét các từ có dạng: ω0 # ω1 # … # ωk trên bộ chữ cái {1, 2, #} sao cho k≥1, mỗi ω là một từ không rỗng trên bộ chữ cái {1, 2} và hơn nữa, ω0 bằng tổng của một số ω khác nào đó khi các từ được xem như là các số nguyên 2-adic. Ta ký hiệu KNAPSACK là ngôn ngữ gồm mọi từ như vậy. 2.4. Định lý: Ngôn ngữ 2-CONSAT thuộc lớp P. 100 2.5. Định lý: Ngôn ngữ SAT là NP-đầy đủ. 2.6. Định lý: Ngôn ngữ CONSAT là NP-đầy đủ. 2.7. Định lý: Ngôn ngữ 3-CONSAT là NP-đầy đủ. 2.8. Định lý: Ngôn ngữ KNAPSACK là NP-đầy đủ. 2.9. Định lý (J. Demetrovics − V.Đ. Thi, 1999): Cho s = (U, F) là một sơ đồ quan hệ trên U. Giả sử U={a1, …, an} và F={A1→B1, …, At→Bt}. Ký hiệu Vs={A | A ⊂ U, A+ ≠ U} (nghĩa là Vs là tập các tập con của U mà không phải là khoá) và m là số nguyên dương, m ≤ |U|. Khi đó bài toán xác định xem có tồn tại một phần tử A∈Vs mà m ≤ |U| hay không là NP-đầy đủ. Chứng minh: Chọn tuỳ ý một tập A sao cho m ≤ |A|. Kiểm tra xem A+≠ U hay không. Việc kiểm tra này là thực hiện trong thời gian đa thức, vì thuật toán xây dựng bao đóng của một tập thuộc tính bất kỳ của s có thời gian tính đa thức. Như vậy thuật toán của chúng ta là bất định và có độ phức tạp tính toán đa thức. Vậy bài toán của ta thuộc lớp NP. Bài toán tập độc lập sau của Garey và Johnson (1979) là bài toán NP-đầy đủ: Cho trước số nguyên dương m và đồ thị G=(V, E), với V là tập các đỉnh và E là tập các cung, E={(ai, aj) | ai, aj∈V}. Ta gọi A là tập độc lập của đồ thị G nếu A là tập con của V và với mọi a, b∈A thì (a, b)∉E. Kiểm tra xem có tồn tại tập độc lập A của G mà m ≤ |A| hay không. Ta sẽ chứng minh rằng bài toán độc lập trên là được chuyển đa thức về bài toán của chúng ta. Cho G=(V, E) là đồ thị mà m ≤ |V|. Xây dựng sơ đồ quan hệ s = (U, F) với U=V và F={{ai, aj}→{a} | (ai, aj)∈E và a∈V \ {ai, aj}}. Rõ ràng s được xây dựng trong thời gian đa thức theo kích thước của G. Theo định nghĩa tập cạnh, rõ ràng E là một siêu đồ thị đơn trên V (định nghĩa về siêu đồ thị và các khái niệm, tính chất liên quan có thể tìm đọc ở bài báo của Vũ Đức Thi “Some results about hypergraph” trong Tạp chí Tin học và Điều khiển học, tập 13, số 2, năm 1997). Từ điều này, ta thấy rằng s là dạng chuẩn BCNF. Do định nghĩa khoá tối thiểu và định nghĩa tập E nên có thể thấy nếu (ai, aj)∈E thì {ai, aj} là một khoá tối thiểu của s. Ngược lại, nếu B∈Ks thì có {ai, aj} sao cho {ai, aj}⊂B. Vì B là một khoá tối thiểu nên ta có {ai,aj}=B. Do đó Ks=E. Như vậy A không phải là khoá của s khi và chỉ khi {ai, aj}⊄A với mọi (ai,aj)∈E. Do đó A không phải là khoá của s khi và chỉ khi A là một tập độc lập của đồ thị G. 2.10. Định nghĩa: Cho s = (U, F) là một sơ đồ quan hệ. Phụ thuộc hàm A→{a} ∈F+ được gọi là phụ thuộc hàm cực đại của s nếu a∉A và với mọi A’⊂A, A’→{a} ∈F+ kéo theo A’=A. 101 Đặt Ta={A | A→{a} là phụ thuộc hàm cực đại của s}. Ta có thể thấy {a} và U∉Ta và Ta là một hệ Sperner trên U (hệ Sperner chính là siêu đồ thị đơn). 2.11. Định lý (J. Demetrovics − V.Đ. Thi, 1994): Bài toán sau là NP-đầy đủ: Cho một sơ đồ quan hệ s = (U, F) và hai thuộc tính a, b, quyết định xem có hay không phụ thuộc hàm cực đại A→{a} sao cho b∈A. Chứng minh: Với b, ta chọn bất định tuỳ ý một tập con A của U sao cho b∈A. Vì thuật toán tính bao đóng của A có độ phức tạp tính toán đa thức và theo định nghĩa của phụ thuộc hàm cực đại, ta xác định được A∈Ta hay không. Rõ ràng rằng thuật toán này là bất định có độ phức tạp tính toán đa thức. Vậy bài toán này thuộc lớp NP. Bây giờ ta cần chỉ ra rằng bài toán trên là NP-khó, có nghĩa là có một bài toán NP-đầy đủ chuyển về bài toán của ta nhờ một thuật toán có độ phức tạp tính toán đa thức. Có thể thấy rằng bài toán dưới đây về việc xác định thuộc tính cơ bản của sơ đồ quan hệ là NP-đầy đủ. Cho sơ đồ quan hệ s = (U, F) và thuộc tính a. Xác định có tồn tại hay không một khoá tối thiểu của s chứa a (a gọi là thuộc tính cơ bản của s). Bài toán này được đưa về bài toán của ta nhờ một thuật toán có độ phức tạp tính toán đa thức như được chứng minh dưới đây. Giả sử s’ = (P, F’) là một sơ đồ quan hệ trên P. Không mất tính chất tổng quát, ta giả thiết rằng P không là một khoá tối thiểu của s’, có nghĩa là nếu A∈Ks thì A⊂P. Vì việc tìm một khoá tối thiểu của một sơ đồ quan hệ cho trước được giải quyết bằng một thuật toán đa thức, ta có thể tìm một khoá tối thiểu C của s’. Bây giờ ta xây dựng sơ đồ quan hệ s = (U, F) như sau: U = P∪{a}, ở đây a∉P và F = F’∪C→{a}. Hiển nhiên s được xây dựng trong thời gian đa thức theo kích thước của P và F’. Rõ ràng C∈Ks. Trên cơ sở kiến trúc s và định nghĩa của khoá tối thiểu, ta thấy nếu A∈Ks’ thì A∈Ks. Ngược lại, nếu B là một khoá tối thiểu của s thì do C→{a}∈F, ta có a∉B. Mặt khác, do định nghĩa của khoá tối thiểu, ta có B∈Ks’. Như vậy ta có Ks’=Ks. Vì C∈Ks và a∉U, nên nếu B→{a} là một phụ thuộc hàm cực đại của s thì B∈Ks. Có thể thấy rằng nếu A∈Ks’ thì A→{a}∈F+. Phù hợp với định nghĩa của phụ thuộc hàm cực đại, ta có A→{a} là một phụ thuộc hàm cực đại của s. Do đó b là một thuộc tính cơ bản của s’ khi và chỉ khi tồn tại một phụ thuộc hàm cực đại A→{a} của s để b∈A. 2.12. Định nghĩa: Bài toán A được gọi là co-NP-đầy đủ nếu bài toán phủ định của A là NP-đầy đủ. Những khái niệm khoá của file dữ liệu và khoá của sơ đồ quan hệ đóng vai trò rất quan trọng trong việc xử lý dữ liệu. Chúng dùng để tìm kiếm các bản ghi và 102 nhờ có chúng người ta mới tìm cách tiến hành xử lý dữ liệu được. Dưới đây là một bài toán co-NP-đầy đủ liên quan đến việc so sánh giữa hai tập khoá của sơ đồ quan hệ và file dữ liệu. Gottlob và Libkin đã chỉ ra rằng bài toán phần bù giới hạn các tập con (SDC- Subset delimiter complementarity) sau là co-NP-đầy đủ. 2.13. Định lý (G. Gottlob − L. Libkin, 1990): Bài toán sau là co-NP-đầy đủ: Cho một tập hữu hạn T, hai họ P={P1, …, Pn} và Q={Q1, …, Qm} các tập con của T. Kiểm tra xem với mọi A⊂T có tồn tại Pi để Pi⊂A hoặc có Qj để A⊂Qj, với 1≤i≤n, 1≤j≤m. Gottlob và Libkin cũng chứng minh rằng nếu Q1, …, Qm là một hệ Sperner trên T thì bài toán trên vẫn là co-NP-đầy đủ. Bài toán SDC này sẽ được chứng tỏ chuyển đa thức về bài toán dưới đây. Ký hiệu Lr và Ls tương ứng là tập tất cả các khoá của quan hệ r và sơ đồ quan hệ s. Bài toán kiểm tra Lr⊂Ls hay không cũng là co-NP-đầy đủ. 2.14. Định lý (J. Demetrovics − V.Đ. Thi, 1993): Bài toán sau là co-NP-đầy đủ: Cho quan hệ r và sơ đồ quan hệ s = (U, F), kiểm tra xem Lr có là tập con của Ls hay không. Chứng minh: Đối với mỗi A⊂U, ta kiểm tra rằng A là hoặc không là một khoá của r bằng một thuật toán đa thức. Từ thuật toán tìm bao đóng A+ và định nghĩa khoá của sơ đồ quan hệ, ta cũng có thể kiểm tra trong thời gian đa thức A là hoặc không là khoá của s. Do đó ta chọn tuỳ ý một tập con A⊂U sao cho A là khoá của r nhưng không là khoá của s. Như vậy, vấn đề của ta thuộc co-NP. Xét bài toán SDC với tập hữu hạn T và hai họ P={P1, …, Pn}, Q={Q1, …, Qm}, ở đây Q là một hệ Sperner trên T. Ký hiệu P’ = {Pi∈P | không tồn tại Pj để Pj⊂Pi, 1≤i, j≤n}. Rõ ràng P’ là tập các phần tử nhỏ nhất của P và P’ là một hệ Sperner trên T. Từ P ta có thể tính P’ trong thời gian đa thức theo |P| và |T|. Dễ thấy {T, P’, Q} là một thể hiện tương đương của {T, P, Q}. Từ đó ta có thể giả thiết rằng P là một hệ Sperner trên T. Ta sẽ chứng minh rằng bài toán SDC được dẫn về bài toán của ta bằng một thuật toán thời gian đa thức. Đặt U = T, s = (U, F), ở đây F = {P1→U, …, Pn→U}. Đặt M = {Qi \ {a} | i=1, 2, …, m và a∈U} = {M1, …, Mt}. Xây dựng quan hệ r = {h0, h1, …, ht} như sau: Với mỗi a∈U, h0(a)=0; hi(a)=0 nếu a∈Mi và hi(a)=i trong trường hợp ngược lại, với i=1, 2, …, t. Rõ ràng r và s được xây dựng trong thời gian đa thức theo kích thước |T|, |P| và |Q|. Có thể thấy rằng Fr và s = (U, F) là dạng chuẩn BCNF. 103 Do s là BCNF nên với mỗi A⊂U, ta có A+=A hoặc A+=U. Từ định nghĩa của khoá, đối với mỗi khoá A của s đều có một Pi sao cho Pi⊂A, ở đây 1≤i≤n. Có thể thấy rằng Q là tập phản khoá của r. Do Fr là BCNF nên với mỗi A⊂U, HFr(A)=U hoặc HFr(A)=A, ở đây HFr(A)={a∈U | (A, {a})∈Fr}. Từ định nghĩa phản khoá của r, ta thấy A là khoá của r khi và chỉ khi với mọi i=1, 2, …, m, A⊄Qi. Vậy Lr⊂Ls khi và chỉ khi với mỗi A⊂T, với mỗi i=1, 2, …, m, A⊄Qi thì có một Pj để Pj⊂A. Từ đây ta thấy rằng bài toán SDC được dẫn về bài toán của ta bằng một thuật toán thời gian đa thức. 104 TÀI LIỆU THAM KHẢO [1] Phan Đình Diệu, Lý thuyết ôtômat và thuật toán, NXB Đại học và Trung học chuyên nghiệp, Hà Nội, 1977. [2] Đỗ Đức Giáo, Đặng Huy Ruận, Văn phạm và ngôn ngữ hình thức, NXB Khoa học và Kỹ thuật, Hà Nội, 1991. [3] Đỗ Đức Giáo, Toán rời rạc, NXB Đại học Quốc Gia Hà Nội, Hà Nội, 2000. [4] Lê Mạnh Thạnh, Nhập môn ngôn ngữ hình thức và ôtômat, NXB Giáo dục, Đà Nẵng, 1998. [5] Vũ Đức Thi, Thuật toán trong tin học, NXB Khoa học và Kỹ thuật, Hà Nội, 1999. [6] Bùi Minh Trí, Tối ưu hoá tổ hợp, NXB Khoa học và Kỹ thuật, Hà Nội, 2003. [7] Phan Thị Tươi, Trình Biên Dịch, NXB Đại học Quốc Gia TP. Hồ Chí Minh, TP. Hồ Chí Minh, 2001. [8] A.V. Aho, J.D. Ullman, The theory of parsing, Translation and compiling, Vol. 1, 2, Prentice-Hall, Englewood Cliffs, 1972. [9] J.E. Hopcroft, J.D. Ullman, Formal languages and their ralation to automata, Addison Wesley, Reading Mass. London, 1969. [10] J.E. Hopcroft, J.D. Ullman, Introduction to formal language theory, Addison Wesley, Reading Mass. London, 1979. [11] K.H. Rosen, Discrete mathematics and its applications, Mc Graw-Hill, New York, 1994. [12] A. Salomaa, Formal languages, Academic Press, New York, 1973. 105