Giáo trình Tin học lý thuyết - Võ Huỳnh Trâm

115 trang huongle 4430

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Tin học lý thuyết - Võ Huỳnh Trâm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_tin_hoc_ly_thuyet_vo_huynh_tram.pdf

Nội dung text: Giáo trình Tin học lý thuyết - Võ Huỳnh Trâm

Giáo trình Tin học lý thuyết By: ThS. Võ Huỳnh Trâm
Giáo trình Tin học lý thuyết By: ThS. Võ Huỳnh Trâm Online: CONNEXIONS Rice University, Houston, Texas
This selection and arrangement of content as a collection is copyrighted by ThS. Võ Huỳnh Trâm. It is licensed under the Creative Commons Attribution 3.0 license ( Collection structure revised: July 30, 2009 PDF generated: February 5, 2011 For copyright and attribution information for the modules contained in this collection, see p. 107.
Table of Contents 1 Bổ túc toán 1 2 Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh 7 3 Ôtômat hữu hạn và biểu thức chính quy 13 4 Văn phạm phi ngữ cảnh 41 5 Ôtômát đẩy xuống 67 6 Văn phạm chính quy và các tính chất 79 7 Máy Turing 89 Attributions 107
Chương 1 Bổ túc toán1 1.1 TẬP HỢP (Sets) Một tập hợp là tập các đối tượng không có sự lặp lại. Mỗi đối tượng trong tập hợp được gọi là phần tử (element) của tập hợp đó. 1.1.1 Ký hiệu tập hợp Nếu số phần tử trong một tập hợp không quá lớn, hay nói cách khác – tập hợp là hữu hạn, tập hợp có thể được đặc tả bằng cách liệt kê các phần tử của nó. Thí dụ 1.1 : D xác định tập hợp các ngày trong tuần : D = { Mon, Tues, Wed, Thurs, Fri, Sat, Sun } Các phần tử trong tập hợp viết cách nhau bởi dấu “, “ và đặt trong cặp dấu { và }. Không có sự bắt buộc về thứ tự liệt kê các phần tử trong tập hợp. Chẳng hạn, tập hợp D cũng tương đương với tập hợp sau : D = { Mon, Wed, Fri, Thurs, Sun, Tues, Sat } Nếu phần tử x là thành phần của tập hợp A, ta viết x [U+F0CE] A (đọc là x thuộc A), và nếu x không là phần tử của A, ta viết x [U+F0CF] A (đọc là x không thuộc A). Chẳng hạn : Mon [U+F0CE] D nhưng Kippers [U+F0CF] D. Nếu một tập hợp chứa một số khá lớn các phần tử hay thậm chí là một số vô hạn, người ta có thể không liệt kê tất cả các phần tử mà đặc tả tập hợp theo một số tính chất đặc trưng của nó. Thí dụ 1.2 : D = { x [U+F07C] x là một ngày trong tuần } P = { y [U+F07C] y là số nguyên tố } X = { x [U+F0BD] x > 2 } Mọi tập hợp đều chứa các phần tử thuộc vào một không gian xác định nào đó, ký hiệu là U. Không gian tương ứng có thể được định nghĩa là một tập số nguyên, số thực, Một trường hợp đặc biệt của tập hợp là tập hợp rỗng (empty set). Tập hợp này không có chứa bất kỳ phần tử nào, ký hiệu bởi [U+F0C6] hoặc { }. Ta nói tập hợp A là tập hợp con (subset) của tập hợp B khi mọi phần tử của A là thành phần của B ( ký hiệu A [U+F0CD] B). Ngược lại, A không là tập con của B (A [U+F0CB] B ). Thí dụ 1.3 : { 1, 2, 4 } [U+F0CD] { 1, 2, 3, 4, 5 } nhưng { 2, 4, 6 } [U+F0CB] { 1, 2, 3, 4, 5 } Có thể suy ra rằng tập hợp A [U+F0CD] U và [U+F0C6] [U+F0CD] A, [U+F022]A Hai tập hợp A và B được gọi là bằng nhau (A = B), khi A [U+F0CD] B và B [U+F0CD] A Thí dụ 1.4 : { 1, 2, 3, 4 } = { 2, 1, 4, 3 } nhưng { 1, 2, 3, 4 } [U+F0B9] { 2, 1, 3, 5 } Tập hợp tất cả các tập hợp con của tập A được gọi là tập lũy thừa (power set) của A và xác định bởi 2A. Thí dụ 1.5 : Giả sử A = { 1, 2, 3 } 1This content is available online at . 1
2 CHƯƠNG 1. BỔ TÚC TOÁN Thì 2A = { [U+F0C6], {1 }, {2 }, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} } 1.1.2 Các phép toán trên tập hợp Các toán tử cơ bản trên tập hợp bao gồm các toán tử một ngôi (unary) và hai ngôi (binary) như sau : 1) Phép phần bù (complement) : A’ = {x [U+F07C] x [U+F0CE] A} 2) Phép hợp (union) : A [U+F0C8] B = {x [U+F07C] x [U+F0CE]A hoặc x [U+F0CE]B} 3) Phép giao (intersection) : A [U+F0C7] B = {x [U+F07C] x [U+F0CE]A và x [U+F0CE]B} 4) Phép trừ (difference) : A \ B = {x [U+F07C] x [U+F0CE]A nhưng x [U+F0CF]B} 5) Tích Đecac : A [U+F0B4] B = {(a,b) [U+F07C] a [U+F0CE]A và b[U+F0CE]B} Thí dụ 1.6 : Cho A = {1, 2} và B = {2, 3} Ta có : A [U+F0C8] B = {1, 2, 3} A [U+F0C7] B = {2} A \ B = {1} A [U+F0B4] B = {(1, 2 ), (1, 3), (2, 2), (2, 3)} 2A = {[U+F0C6], {1}, {2}, {1, 2}} Lưu ý : Nếu A và B lần lượt có số phần tử là n và m thì tập hợp A [U+F0B4] B có n [U+F0B4] m phần tử và tập 2A có 2n phần tử. 1.2 QUAN HỆ (Relations) Cho hai tập hợp A và B. Một quan hệ hai ngôi R giữa A và B là tập hợp chứa tất cả các tập hợp con của A [U+F0B4] B mà thành phần thứ nhất A được gọi là miền xác định (domain) của R, còn B gọi là miền giá trị (range) của R (có thể trùng với miền xác định). Chúng ta sẽ thường dùng quan hệ hai ngôi mà miền xác định và miền giá trị cùng thuộc một tập hợp S nào đó. Trong trường hợp này, ta gọi đây là một quan hệ trên S. Nếu R là một quan hệ và (a,b) là một cặp trong R thì ta viết aRb. Thí dụ 1.7 : Cho S = { 0, 1, 2, 3} . Quan hệ "thứ tự nhỏ hơn" trên S được xác định bởi tập : L = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)} . Quan hệ "bằng" trên S được xác định bởi tập : E = {(0, 0), (1, 1), (2, 2), (3, 3)} . Quan hệ "chẵn lẻ" trên S được xác định bởi tập : P = {(0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)} Các tính chất của quan hệ Ta gọi một quan hệ R trên tập S là: [U+F0B7] Phản xạ (reflexive) : nếu aRa là đúng [U+F022]a [U+F0CE] S [U+F0B7] Đối xứng (symmetric) : nếu aRb thì bRa [U+F0B7] Bắc cầu (transitive) : nếu aRb và bRc thì aRc Thí dụ 1.8 : . L không là quan hệ phản xạ trên S vì (0, 0) [U+F0CF] L, nhưng E và P là 2 quan hệ mang tính phản xạ. . L không là quan hệ đối xứng trên S vì (0, 1) [U+F0CE] L nhưng (1, 0) [U+F0CF] L, tuy nhiên cả E và P đều mang tính đối xứng. . Cả L, E và P đều là các quan hệ mang tính bắc cầu, nhưng X = {(1, 0),(0, 3)} thì không vì (1, 3) [U+F0CF] X. 1.2.1 Quan hệ tương đương Một quan hệ R trên tập S có đủ các tính chất phản xạ, đối xứng và bắt cầu được gọi là quan hệ tương đương. Thí dụ 1.9 :E và P là các quan hệ tương đương, còn L và X không là các quan hệ tương đương trên S.
3 Một tính chất quan trọng của quan hệ tương đương là nếu R là quan hệ tương đương trên tập S thì R phân hoạch tập S thành các lớp tương đương (equivalence class) Si không rỗng và rời nhau, tức là S = S1 [U+F0C8] S2 [U+F0C8] và với mọi i [U+F0B9] j ta có : + Si C¸Sj = Æ + Với mỗi a,b cùng thuộc Si thì aRb là đúng. + Với mỗi a [U+F0CE] Si và b [U+F0CE] Sj thì aRb là sai. Lưu ý rằng số lớp tương đương có thể là vô hạn. Vậy nếu R là quan hệ tương trên S và a [U+F0CE] S, ta có : Si = [a] = {b ˆIS [U+F0BD] aRb} Thí dụ 1.10 : . E có 4 lớp tương đương khác nhau: [0] = {0}, [1] = {1}, [2] = {2} và [3] = {3} . P có 2 lớp tương đương khác nhau: [0] = [2] = {0, 2} và [1] = [3] = {1, 3} 1.2.2 Bao đóng của quan hệ Giả sử P là tập hợp một số tính chất của các quan hệ, bao đóng P (P - closure) của một quan hệ R trên tập S là quan hệ nhỏ nhất có chứa tất cả các cặp của R thoả mãn các tính chất trong P. [U+F0B7] Bao đóng bắc cầu R+ của R được xác định như sau : i) Nếu (a,b) thuộc R thì (a,b) thuộc R+. ii) Nếu (a,b) thuộc R+ và (b,c) cũng thuộc R thì (a,c) thuộc R+. iii) Không còn gì thêm trong R+. [U+F0B7] Bao đóng phản xạ và bắc cầu R* của R được xác định như sau : R* = R+ [U+F0C8] {(a, a)[U+F0BD] a [U+F0CE] S} Thí dụ 1.11 :Cho quan hệ R = {(1, 2), (2, 2), (2, 3)} trên tập hợp S = {1, 2, 3} Khi đó ta có : R+ = {(1, 2), (2, 2), (2, 3), (1, 3)} R* = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} 1.3 PHÉP CHỨNG MINH QUY NẠP Phần lớn các định lý trong giáo trình sẽ được chứng minh bằng phương pháp quy nạp toán học : Giả sử ta cần chứng minh một mệnh đề P(n) với n là một số nguyên không âm. Nguyên lý quy nạp toán học cho P(n) được chứng minh theo 2 bước như sau : i) P (0) , và ii) P( n - 1) kéo theo P (n), [U+F022]n [U+F0B3] 1. Bước (i) được gọi là cơ sở quy nạp, bước (ii) được gọi là bước quy nạp với P(n-1) là giả thiết quy nạp. Thí dụ 1.12 :Dùng quy nạp, chứng minh biểu thức : Pn 2 n(n+1)(2n+1) i=0 i = 6 Cơ sở quy nạp : Thay n = 0 trong vế phải của biểu thức và nhận thấy cả 2 vế đều bằng 0 [U+F0DE] P (0) luôn đúng. Bước quy nạp : Thay n bởi n - 1 để có được giả thiết quy nạp P(n-1), sau đó tìm cách để chứng minh P(n), tức chứng minh [U+F022]n [U+F0B3] 1, ta có : Pn - 1 2 (n - 1) n (2n -1) Pn 2 n (n+1)(2n +1) i = 0 i = 6 ⇒ i = 0 i = 6 Ta có nhận xét rằng : Pn 2 Pn - 1 2 2 i = 0 i = i = 0 i + n (n -1) n (2n -1) 2 n (n +1)(2n +1) 6 + n = 6 Vậy nếu ta vận dụng giả thiết quy nạp thì chỉ còn phải chứng minh biểu thức : Với một vài phép biến đổi đại số đơn giản, biểu thức trên có thể được chứng minh dễ dàng. Hay P(n) được chứng minh, [U+F022]n.
4 CHƯƠNG 1. BỔ TÚC TOÁN 1.4 ĐỒ THỊ VÀ CAˆY 1.4.1 Đồ thị (Graph) Một đồ thị, ký hiệu G = (V, E), bao gồm một tập hữu hạn các đỉnh V (còn gọi là nút) và một tập các cạnh E nối giữa 2 nút. Thí dụ 1.13 :Đồ thị cho bởi :V = {1, 2, 3, 4, 5} và E = {(n, m) [U+F07C] n + m = 4 hoặc n + m = 7} Figure 1.1 Hình 1.1 - Ví dụ về đồ thị Một đường đi (path) trên một đồ thị là dãy các đỉnh v1, v2 , . . ., vk, k [U+F0B3] 1, sao cho trong đó có một cạnh (vi ,vi +1) cho mỗi i, 1 [U+F0A3] i < k. Độ dài của đường đi là k - 1. Nếu v1 = vk thì đường đi là một chu trình. Chẳng hạn : 1, 3, 4 là một đường đi trong đồ thị trên. Đồ thị có hướng (directed graph) Một đồ thị có hướng cũng là dạng đồ thị được xác định bởi G = (V, E), trong đó V là tập các đỉnh, còn E là tập các đỉnh có thứ tự gọi là các cung (hay các đường nối có hướng giữa 2 đỉnh). Ký hiệu một cung từ v đến w có dạng v [U+F0AE] w. Thí dụ 1.14 : Đồ thị có hướng G = ({1, 2, 3, 4 }, { i [U+F0AE] j [U+F07C] i < j }) Figure 1.2 Hình 1.2 - Một đồ thị có hướng Một đường đi trên một đồ thị có hướng là dãy các đỉnh v1, v2 , . . ., vk, k [U+F0B3] 1, sao cho với mỗi i, 1 [U+F0A3] i < k, có một cung từ vi đến vi +1. Chẳng hạn 1 [U+F0AE] 2 [U+F0AE] 3 [U+F0AE] 4 là một
5 đường đi trên đồ thị định hướng trên (từ 1 đến 4). 1.4.2 Cây (trees) Cây (cây định hướng có thứ tự) là một đồ thị có hướng với các tính chất sau : i) Có một nút đỉnh gọi là nút gốc ii) Mỗi nút còn lại đều được dẫn ra từ một nút cha ở trên nó : - Các nút có dẫn ra nút con sau nó được gọi là nút trung gian hay nút trong. - Các nút không dẫn ra nút con gọi là nút lá. iii) Thứ tự duyệt trên cây là từ trái sang phải. Trong một cây, người ta thường dùng các khái niệm nút cha và nút con để lần lượt chỉ thứ tự trước và sau của sự phát sinh nút từ nút gốc trên cây. Nếu có một đường đi từ nút v1 đến nút v2 thì v1 được gọi là nút cha của v2 và ngược lại, v2 sẽ là nút con của nút v1. Ta thường vẽ cây với nút gốc ở trên cùng và các cung chỉ xuống phía dưới, do vậy các ký hiệu mũi tên trở nên không còn cần thiết nữa. Các nút con của mỗi nút trên cây sẽ được vẽ lần lượt từ trái qua phải theo thứ tự đã xác định. Thí dụ 1.15 : Cây minh họa cấu trúc cú pháp của một câu đơn trong ngôn ngữ tiếng Việt "An là sinh viên giỏi" Figure 1.3 Hình 1.3 - Cây minh họa một câu đơn BÀI TẬP CHƯƠNG I 1.1. Nếu không gian tập hợp là tập các số nguyên dương nhỏ hơn 20. Hãy viết rõ các phần tử trong các tập hợp được xác định như sau : 1. { x [U+F0BD] x + 2 < 10} 2. { x [U+F0BD] x là số nguyên tố } 3. { x [U+F0BD] x = x2} 4. { x [U+F0BD] 2x = 1}
6 CHƯƠNG 1. BỔ TÚC TOÁN 5. { x [U+F0BD] 3x < 20} 1.2. Cho tập hợp S = {0, 1, 2, 3, 4, 5, 6} Hãy viết rõ các phần tử trong các tập hợp được xác định như sau : 1. { x [U+F0BD] x [U+F0CE] S và x chẳn } 2. { x [U+F0BD] x [U+F0CE] S và x [U+F0B3] x2 + 1 } 1.3. Cho A = {0, 1, 2} và B = {0, 3, 4}. Hãy viết rõ các tập hợp sau : A [U+F0C8] B;A [U+F0C7] B;A \ B ; A x B và 2A 1.4. Cho ví dụ về quan hệ : a) Phản xạ và đối xứng, nhưng không bắc cầu. b) Phản xạ và bắc cầu, nhưng không đối xứng. c) Đối xứng và bắc cầu, nhưng không phản xạ. Trong mỗi trường hợp trên, chỉ rõ tập hợp trên đó quan hệ được xác định. 1.5. Chứng minh các quan hệ sau đây là các quan hệ tương đương và cho các lớp tương đương của chúng. a) Quan hệ R1 trên các số nguyên định nghĩa bởi : iR1j khi và chỉ khi i = j. b) Quan hệ R2 trên một tập thể người định nghĩa bởi : pR2q khi và chỉ khi p, q sinh cùng ngày và cùng năm. 1.6. Cho tập hữu hạn A. Hãy tìm những quan hệ tương đương trên A có số các lớp tương đương là lớn nhất hay nhỏ nhất. 1.7. Cho hai tập hợp sau A = {2, 3, 4, 5} và B = {1, 3, 5, 7, 9}. Giả sử R là quan hệ : R = {(x, y) [U+F0CE] A [U+F0B4] B [U+F07C] x < y} Hãy liệt kê các cặp quan hệ thứ tự trong R. 1.8. Tìm bao đóng bắc cầu, bao đóng phản xạ và bắc cầu của quan hệ được cho như sau trên S = { 1, 2, 3, 4, 5}: {(1, 2), (2, 3), (3, 4), (5, 4)} 1.9. Cho S = {0, 1, 2} và R = {(0, 1), (1, 2)}. Tìm R* và R+.
Chương 2 Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh1 2.1 ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI (LBA) Ta gọi Ôtômát tuyến tính giới nội (Linear Bounded Automata - LBA) là một máy Turing không đơn định và không có khả năng nới rộng vùng làm việc ra khỏi mút trái và mút phải của chuỗi nhập. Nó phải thỏa hai điều kiện sau : 1) Bộ chữ cái nhập của nó có chứa thêm hai ký hiệu đặc biệt [U+F0CB] và $ dùng làm ký hiệu đánh dấu mút trái và mút phải. 2) LBA không thực hiện phép chuyển sang trái (L) từ [U+F0CB] và không thực hiện phép chuyển sang phải (R) từ $, và cũng không viết các ký hiệu khác lên [U+F0CB] và $. LBA đơn giản là một máy Turing nhưng thay vì sử dụng một băng không giới hạn cho việc tính toán, nó bị hạn chế chỉ trong phạm vi băng chứa chuỗi nhập x với hai ô chứa các ký hiệu đánh dấu cận đầu mút. Sự giới hạn này làm cho việc tính toán phải thông qua một số các hàm tuyến tính trên độ dài chuỗi, do đó ta gọi mô hình này là ôtômát tuyến tính giới nội. LBA không dùng các ô trống ở trên băng về phía trái và phía phải của chuỗi nhập, vì vậy ký hiệu khoảng trắng B (Blank) như đã dùng ở máy Turing là không cần dùng ở đây. Trái lại, để LBA nhận biết được giới hạn bên trái và giới hạn bên phải của chuỗi nhập, ta phải đưa thêm vào bộ chữ cái nhập [U+F053] hai ký hiệu đặc biệt [U+F0CB], $ để đánh dấu mút trái và mút phải của chuỗi. Vậy, tại thời điểm bắt đầu, chuỗi nhập đưa vào ở trên băng sẽ có dạng [U+F0CB] w $, trong đó w [U+F0CE] ([U+F0E5]-{[U+F0CB], $})* là chuỗi cần đoán nhận. Trong quá trình làm việc, khi đầu đọc đọc tới ô có chứa [U+F0CB] hay $, thì phép chuyển tiếp theo sau đó chỉ có thể là đổi trạng thái, chuyển đầu đọc trở lại phía trong phạm vi băng (tức chuyển sang phải khi gặp [U+F0CB] và chuyển sang trái khi gặp $), và không được phép viết ký hiệu gì khác trên băng tại ô đang đọc khi gặp [U+F0CB] và $. Định nghĩa LBA Một cách hình thức, LBA là một hệ thống M(Q, [U+F053], [U+F047],[U+F064],qo,[U+F0CB], $, F), trong đó các thành phần Q, [U+F053], [U+F047], qo, F vẫn như đã định nghĩa ở máy Turing, còn [U+F0CB], $ [U+F0CE] [U+F053] và hàm chuyển : [U+F064]:Q [U+F0B4] [U+F047] [U+F0AE] (Q [U+F0B4] [U+F047] [U+F0B4] { L, R}) phải thỏa mãn điều kiện: • Nếu (p, Y, E) [U+F0CE] [U+F064](q, [U+F0CB]) thì Y = [U+F0CB] và E = R • Nếu (p, Y, E) [U+F0CE] [U+F064](q, $) thì Y = $ và E = L Ngôn ngữ được chấp nhận bởi LBA 1This content is available online at . 7
8 CHƯƠNG 2. ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ CẢNH Ta định nghĩa ngôn ngữ L(M) được đoán nhận bởi LBA M là tập hợp : L(M) = { w [U+F07C] w [U+F0CE] ([U+F053] -{[U+F0CB], $})* và qo[U+F0CB]w$ `M* [U+F061]q[U+F062] với q [U+F0CE] F và [U+F061][U+F062] [U+F0CE] [U+F047]*} Chú ý rằng các ký hiệu đánh dấu hai đầu mút ngay từ hình thái bắt đầu chúng đã có mặt trên băng nhập, nhưng chúng không được xem như thuộc một phần của chuỗi được chấp nhận hay không được chấp nhận bởi LBA. Vì đầu đọc của LBA không thể dịch chuyển ra ngoài phần chuỗi nhập nên chúng ta không cần định nghĩa các khoảng trống (ký hiệu Blank) phía bên phải của $. 2.2 VĂN PHẠM CẢM NGỮ CẢNH (CSG) Ta gọi văn phạm cảm ngữ cảnh (Context Sensitive Grammar - CSG) là một hệ thống G (V, T, P, S), trong đó: 1. V là một tập hữu hạn các biến hay ký hiệu không kết thúc. 2. T là một tập hữu hạn các ký hiệu cuối, V [U+F0C7] T = [U+F0C6] 3. P là tập hữu hạn các luật sinh dạng [U+F061] [U+F0AE] [U+F062] trong đó [U+F061], [U+F062] [U+F0CE] (V [U+F0C8] T)*, chuỗi [U+F061] phải có chứa biến và ràng buộc [U+F0F7] [U+F061][U+F0F7] [U+F0A3] [U+F0BD][U+F062][U+F0BD] 4. S [U+F0CE] V là ký hiệu bắt đầu. Ta định nghĩa ngôn ngữ do văn phạm cảm ngữ cảnh G sinh ra là L(G) = { w [U+F07C] w [U+F0CE] [U+F053]* và S [U+F0DE]* w} L(G) được gọi là ngôn ngữ cảm ngữ cảnh (Context Sensitive Language - CSL). Thuật ngữ “cảm ngữ cảnh” có xuất xứ từ một dạng chuẩn của văn phạm dạng này, trong đó mỗi luật sinh có dạng [U+F061]1A[U+F061]2 [U+F0AE] [U+F061]1[U+F062][U+F061]2 với [U+F062] [U+F0B9] [U+F065], cho thấy một biến A chỉ có thể được thay thế bởi một chuỗi [U+F062] (khác rỗng) trong “ngữ cảnh” [U+F061]1 - [U+F061]2. Điều đó không giống như trong văn phạm phi ngữ cảnh, với các luật sinh có dạng A [U+F0AE] [U+F062] ([U+F0BD][U+F062][U+F0BD][U+F0B3] 0), sự thay thế này không đòi hỏi ngữ cảnh. Thí dụ 8.1 : Xét CSG G (V, T, P, S) với V ={ S, B, C}, [U+F0E5] ={a, b, c} và P gồm các luật sinh như sau : 1) S [U+F0AE] aSBC 2) S [U+F0AE] aBC 3) CB [U+F0AE] BC 4) aB [U+F0AE] ab 5) bB [U+F0AE] bb 6) bC [U+F0AE] bc 7) cC [U+F0AE] cc Một cách phi hình thức, bằng cách áp dụng một số luật sinh cho các chuỗi dẫn xuất sinh ra ngôn ngữ, ta dễ thấy rằng văn phạm G sinh ra ngôn ngữ có dạng : L = {anbncn[U+F0BD] n [U+F0B3] 1} Thật vậy, với luật sinh (1) và (2) ta có chuỗi dẫn xuất S [U+F0DE]* an(BC)n. Sau đó, bằng cách áp dụng luật sinh (3), mọi biến B sẽ được thay thế lên trước các biến C trong chuỗi dẫn xuất : an(BC) [U+F0DE]* anBnCn. Bởi luật sinh (4) và (5), mọi biến B sẽ được thay thế thành các ký hiệu kết thúc b, và cuối cùng với (6) và (7), mọi biến C cũng sẽ được thay thế thành c. Tóm lại, ta có chuỗi dẫn xuất như sau : S[U+F0DE]* an(BC)n [U+F0DE]* anBnCn [U+F0DE]* anbncn Bài toán thành viên với CSG (Membership) ĐỊNH LÝ 8.1 : Tồn tại giải thuật để xác định với mọi ngôn ngữ cảm ngữ cảnh CSG G(V, T, P, S) bất kỳ và một chuỗi nhập w [U+F0CE] T*, liệu chuỗi w có thuộc ngôn ngữ L(G) hay không. Chứng minh Giả sử [U+F07C] w [U+F07C] = n. Ta lập đồ thị mà mỗi đỉnh là một chuỗi thuộc (V [U+F0C8] T)* có độ dài nhỏ hơn hoặc bằng n, có một cung từ đỉnh [U+F061] đến đỉnh [U+F062] nếu [U+F061] [U+F0DE]G
9 [U+F062]. Như vậy một đường trong đồ thị đó tương ứng với một suy dẫn trong G. Vậy w [U+F0CE] L(G) khi và chỉ khi có một đường đi từ đỉnh bắt đầu S tới đỉnh w trong đồ thị. Dùng bất cứ giải thuật nào cho phép tìm đường nối hai đỉnh trong đồ thị (đã có nhiều thuật toán như thế), ta sẽ xác định được phải chăng đã có đường đi từ đỉnh S tới đỉnh w. Thí dụ 8.2 : Xét CSG G (V, T, P, S) với các luật sinh được cho như trong Thí dụ 8.1 trên và xét chuỗi nhập w = abbc. Ta cần xác định xem liệu chuỗi w [U+F0CE] L(G)? Để tìm đường đi từ đỉnh S tới đỉnh abbc trong đồ thị nói trên ta có thể dùng phương pháp “vết dầu loang” như sau: Lập các R(i), i = 0, 1, 2, theo quy tắc sau: R(0) = { S } R(i) = R(i -1) [U+F0C8] { [U+F062] [U+F07C] [U+F061] [U+F0DE] [U+F062] với [U+F061] [U+F0CE] R(i -1) và [U+F07C] [U+F062] [U+F07C] [U+F0A3] [U+F07C] w [U+F07C] } Do R(0) [U+F0CD] R(1) [U+F0CD] [U+F0CD] R(i) [U+F0CD] R(i +1) [U+F0CD] [U+F0CD] tập các đỉnh, vậy tồn tại số k nào đó sao cho: R(k) = R(k +1) = R(k +2) = Do đó quá trình thành lập các R(i) sẽ có thể ngừng sau k bước. Và w [U+F0CE] L(G) khi và chỉ khi có i [U+F0A3] k để cho w [U+F0CE] R(i). Trong thí dụ trên, giả sử khi ta xét [U+F07C] w [U+F07C]= 4, ta có: R(0) = { S } R(1) = {S, aSBC, aBC} R(2) = {S, aSBC, aBC, abC} R(3) = {S, aSBC, aBC, abC, abc} R(4) = R(3) Vậy chuỗi abbc không thuộc L(G). 2.3 SỰ TƯƠNG ĐƯƠNG GIỮA LBA VÀ CSG Chúng ta chú ý rằng LBA có thể chấp nhận các chuỗi rỗng [U+F065], còn CSG không thể sinh ra chuỗi rỗng. Ngoài trường hợp đó ra thì LBA sẽ chấp nhận chính xác tất cả các chuỗi được sinh ra từ CSG. ĐỊNH LÝ 8.2 : Nếu L là một CSG thì L sẽ được chấp nhận bởi một LBA nào đó. Chứng minh Cách chứng minh định lý này cũng tương tự như cách chứng minh của định lý 7.9 ở chương trước về sự tương đương giữa lớp ngôn ngữ sinh từ văn phạm loại 0 với lớp ngôn ngữ mà máy Turing chấp nhận, chỉ khác là ở đây không cần dùng một băng nhập thứ hai để phát sinh các dạng câu theo chuỗi dẫn xuất lần lượt theo các suy dẫn của văn phạm, mà chỉ cần dùng rãnh thứ hai trên băng nhập của LBA vào việc đó. Cho G = (V, T, P, S) là một CSG, ta xây dựng ôtômát LBA M như sau: Băng nhập của LBA gồm hai rãnh : rãnh 1 chứa chuỗi nhập w với các ký hiệu đánh dấu [U+F0CB], $ ở hai đầu, rãnh 2 dùng để phát sinh các dạng câu [U+F061]. Trạng thái bắt đầu, nếu w = [U+F065] thì M ngừng và không chấp nhận input, nếu không thì đầu đọc viết ký hiệu S ở rãnh 2, ngay dưới ký hiệu bên trái nhất của chuỗi w, tiếp đó M thực hiện quá trình sau: 1) Chọn trong số không đơn định một chuỗi con [U+F062] của chuỗi [U+F061] trên rãnh 2 sao cho [U+F062] [U+F0AE] [U+F067] là một luật sinh trong P. 2) Thay [U+F062] bởi [U+F067], nếu cần thiết ta phải dịch chuyển phần cuối chuỗi sang phải cho đủ chỗ, tuy nhiên nếu dịch chuyển ra ngoài $ thì LBA ngừng và không chấp nhận. 3) (Hình thái hiện tại ở rãnh 1 là [U+F0CB] w $, còn ở rãnh 2 là chuỗi [U+F061], mà S [U+F0DE]G [U+F061] và [U+F07C] [U+F061] [U+F07C] [U+F0A3] [U+F07C] w [U+F07C]). So sánh rãnh 1 và rãnh 2, nếu [U+F061] = w thì LBA ngừng và chấp nhận w. Nếu không thì trở về bước (1). Như vậy khi M chấp nhận chuỗi w, thì S [U+F0DE]G* w. Ngược lại nếu S [U+F0DE]G* w thì mọi dạng câu [U+F061] xuất hiện trong chuỗi dẫn xuất đó đều thoả mãn [U+F07C] [U+F061] [U+F07C] [U+F0A3] [U+F07C] w [U+F07C], bởi vì mọi luật sinh [U+F062] [U+F0AE] [U+F067] trong văn phạm G đều thỏa
10 CHƯƠNG 2. ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ CẢNH [U+F07C] [U+F062] [U+F07C] [U+F0A3] [U+F07C] [U+F067] [U+F07C]. Như vậy M có thể thực hiện chuỗi dẫn xuất đó trên rãnh 2, giữa hai ký hiệu đánh dấu đầu mút [U+F0CB] và $. Vậy M chấp nhận chuỗi nhập w. Tóm lại M sẽ chấp nhận mọi chuỗi sinh ra bởi văn phạm G. ĐỊNH LÝ 8.3 : Nếu L = L(M) với một LBA M (Q, [U+F053], [U+F047],[U+F064],qo,[U+F0CB], $, F) thì L – {[U+F065]} là một ngôn ngữ cảm ngữ cảnh. Chứng minh Cách chứng minh định lý này cũng tương tự như cách chứng minh của định lý 7.10 ở chương trước, bằng cách ta xây dựng một CSG G thực hiện 3 giai đoạn: - Giai đoạn 1: Văn phạm cho phép sinh ra một chuỗi w (chuỗi nhập của M), cũng được chứa trong [U+F0CB], $ và q0. - Giai đoạn 2: Văn phạm lặp lại công việc của M. - Giai đoạn 3: Khi xuất hiện trạng thái q [U+F0CE] F, ta thu về chuỗi w với lưu ý rằng các luật sinh [U+F061] [U+F0AE] [U+F062] đều có [U+F07C] [U+F061] [U+F07C] = [U+F07C] [U+F062] [U+F07C]. Quá trình mô phỏng lại các luật sinh đó bởi các luật sinh của CSG sẽ không có gì vướng mắc. Chỉ ở giai đoạn 3, việc xoá đi các ký hiệu đánh dấu hai đầu mút [U+F0CB] và $, q không được phép làm rút ngắn chuỗi nhập lại. Để giải quyết vướng mắc này, ta gắn các ký hiệu [U+F0CB], $, q kề bên với các ký hiệu của chuỗi nhập mà không để đứng rời ra như trước. Cụ thể, giai đoạn 1 thực hiện bởi các luật sinh trong G sau: S1 [U+F0AE] [a, q0 [U+F0CB] a]S2S1 [U+F0AE] [a, q0[U+F0CB]a$] S2 [U+F0AE] [a, a]S2,S2 [U+F0AE] [a,a$] [U+F022]a [U+F0CE] [U+F053] -{[U+F0CB], $} Các luật sinh trong G cho phép thực hiện giai đoạn 2, giống như LBA M thực hiện (sinh viên tự xây dựng xem như bài tập). Cuối cùng, ở giai đoạn 3, các luật sinh sau đây sẽ được sử dụng, với q [U+F0CE] F: [a, [U+F061]q[U+F062]] [U+F0AE] a [U+F022]a [U+F0CE] [U+F053] -{[U+F0CB], $} và [U+F022][U+F061], [U+F062] có thể có. Chú ý rằng số luật sinh là hữu hạn, vì [U+F061] và / hoặc [U+F062] chỉ gồm [U+F0CB], $ và một ký hiệu nhập vào. Chúng ta cũng có thể xoá thành phần thứ hai của một biến nếu nó liền kề với ký hiệu kết thúc bằng cách dùng các luật sinh dạng: [a, [U+F061]]b [U+F0AE] ab b[a, [U+F061]] [U+F0AE] ba [U+F022]a, b [U+F0CE] [U+F053] -{[U+F0CB], $} và [U+F022][U+F061] có thể có. Như vậy các luật sinh vừa được xây dựng mô tả văn phạm là CSG và có thể chứng minh L(M) - {[U+F065]} = L(G). 2.4 TƯƠNG QUAN GIỮA CÁC LỚP NGÔN NGỮ Ngôn ngữ đoán nhận bởi các văn phạm cũng được phân loại theo tên của từng lớp văn phạm, ta gọi đó là sự phân cấp Chomsky về ngôn ngữ. Có 4 lớp ngôn ngữ đã được giới thiệu – tập đệ quy liệt kê (r.e), ngôn ngữ cảm ngữ cảnh (CSL), ngôn ngữ phi ngữ cảnh (CFL) và tập chính quy (r) tương đương với 4 lớp ngôn ngữ loại 0, 1, 2 và 3. Theo lý thuyết được xây dựng xuyên suốt trong giáo trình này, ta có thể tóm tắt lại như sau: a) L là ngôn ngữ loại 0 khi và chỉ khi L được đoán nhận bởi một máy Turing. b) L là ngôn ngữ loại 1 khi và chỉ khi L được đoán nhận bởi một ôtômát tuyến tính giới nội (sai khác chuỗi rỗng [U+F065]) c) L là ngôn ngữ loại 2 khi và chỉ khi L được đoán nhận bởi một ôtômát đẩy xuống (không đơn định). d) L là ngôn ngữ loại 3 khi và chỉ khi L được đoán nhận bởi một ôtômát hữu hạn (sai khác chuỗi rỗng [U+F065]).
11 Ta cũng cần lưu ý rằng sự phân cấp ngôn ngữ như trên là một bao hàm thức nghiêm ngặt, thể hiện quy luật sau: a) Lớp các ngôn ngữ loại 3 là tập con thực sự của lớp ngôn ngữ loại 2. Thật vậy mọi văn phạm chính quy đều là văn phạm phi ngữ cảnh. Hơn nữa người ta có thể chứng minh rằng ngôn ngữ {0n1n [U+F07C] n [U+F0B3] 1} là một ngôn ngữ phi ngữ cảnh, nhưng không phải là ngôn ngữ chính quy. b) Lớp các ngôn ngữ loại 2 không chứa các chuỗi rỗng là tập con thực sự của lớp ngôn ngữ loại 1. Thật vậy mọi văn phạm phi ngữ cảnh có dạng chuẩn Chomsky đều là văn phạm cảm ngữ cảnh. Hơn nữa người ta có thể chứng minh rằng ngôn ngữ {a 2i [U+F07C] i [U+F0B3] 1} là ngôn ngữ cảm ngữ cảnh nhưng không là ngôn ngữ phi ngữ cảnh. c) Lớp các ngôn ngữ loại 1 là tập con thực sự của lớp các ngôn ngữ loại 0. Thật vậy, mọi văn phạm cảm ngữ cảnh đều là văn phạm cấu trúc không hạn chế. Mặt khác người ta cũng đề xuất được những ngôn ngữ là đệ quy liệt kê (loại 0), mà không cần làm ngữ cảnh (loại 1). Các thí dụ đó được xây dựng dựa trên các khái niệm “đệ quy” và “sự giải được”, mà khuôn khổ giáo trình này không cho phép đề cập đến. Tổng kết chương VIII: Với sự giới thiệu mô hình ôtômát tuyến tính giới nội LBA và lớp ngôn ngữ cảm ngữ cảnh mà nó đoán nhận, mô hình phân cấp ngôn ngữ theo Noam Chomsky đã được hoàn chỉnh. BÀI TẬP CHƯƠNG VIII 8.1. Xây dựng văn phạm cảm ngữ cảnh sinh ra các ngôn ngữ sau: a) { ww | w ˆI (0+1)+} b) { 0k | k = i2 và i 3 1} c) { 0i | i không là số nguyên tố} d) { ai b2i c3i [U+F07C] i 3 1} e) { ai bi ck [U+F07C] i 3 1, k [U+F0A3] 1} 8.2. Thiết kế ôtômát tuyến tính giới nội LBA đoán nhận các ngôn ngữ sau: 1. { an bn cn [U+F07C] n 3 1} b) { ww | w ˆI (a + b + c)*}
12 CHƯƠNG 2. ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ CẢNH
Chương 3 Ôtômat hữu hạn và biểu thức chính quy1 3.1 ÔTÔMÁT HỮU HẠN (FA : Finite Automata) Ôtômát hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các input và output. Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn các cấu hình nội bộ gọi là các trạng thái (states). Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liên quan đến những input đã chuyển qua và xác định các phép chuyển kế tiếp trên dãy input tiếp theo. Trong khoa học máy tính, ta có thể tìm thấy nhiều ví dụ về hệ thống trạng thái hữu hạn, và lý thuyết về ôtômát hữu hạn là một công cụ thiết kế hữu ích cho các hệ thống này. Chẳng hạn, một hệ chuyển mạch như bộ điều khiển (Control Unit) trong máy tính. Một chuyển mạch thì bao gồm một số hữu hạn các cổng (gate) input, mỗi cổng có 2 giá trị 0 hoặc 1. Các giá trị đầu vào này sẽ xác định 2 mức điện thế khác nhau ở cổng output. Mỗi trạng thái của một mạng chuyển mạch với n cổng bất kỳ sẽ là một trường hợp trong 2n phép gán của 0 và 1 đối với các cổng khác nhau. Các chuyển mạch thì được thiết kế theo cách này, vì thế chúng có thể được xem như hệ thống trạng thái hữu hạn. Các chương trình sử dụng thông thường, chẳng hạn trình sọan thảo văn bản hay bộ phân tích từ vựng trong trình biên dịch máy tính cũng được thiết kế như các hệ thống trạng thái hữu hạn. Ví dụ bộ phân tích từ vựng sẽ quét qua tất cả các dòng ký tự của chương trình máy tính để tìm nhóm các chuỗi ký tự tương ứng với một tên biến, hằng số, từ khóa, Trong quá trình xử lý này, bộ phân tích từ vựng cần phải nhớ một số hữu hạn thông tin như các ký tự bắt đầu hình thành những chuỗi từ khóa. Lý thuyết về ôtômát hữu hạn thường được dùng đến nhiều cho việc thiết kế các công cụ xử lý chuỗi hiệu quả. Máy tính cũng có thể được xem như một hệ thống trạng thái hữu hạn. Trạng thái hiện thời của bộ xử lý trung tâm, bộ nhớ trong và các thiết bị lưu trữ phụ ở mỗi thời điểm bất kỳ là một trong những số rất lớn và hữu hạn của số trạng thái. Bộ não con người cũng là một hệ thống trạng thái hữu hạn, vì số các tế bào thần kinh hay gọi là neurons là số có giới hạn, nhiều nhất có thể là 235. Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự nhiên của khái niệm và khả năng ứng dụng đa dạng trong nhiều lĩnh vực thực tế. Ôtômát hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA). Cả hai loại ôtômát hữu hạn đều có khả năng nhận dạng chính xác tập chính quy. Ôtômát hữu hạn đơn định có khả năng nhận dạng ngôn ngữ dễ dàng hơn ôtômát hữu hạn không đơn định, nhưng thay vào đó thông thường kích thước của nó lại lớn hơn so với ôtômát hữu hạn không đơn định tương đương. 1This content is available online at . 13
14 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY 3.1.1 Ôtômát hữu hạn đơn định - DFA (Deterministic Finite Automata) Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -gồm một tập hữu hạn các trạng thái và một tập các phép chuyển từ trạng thái này tới trạng thái khác trên các ký hiệu nhập (input symbols) được chọn từ một bộ chữ cái [U+F053] nào đó. Mỗi ký hiệu nhập có đúng một phép chuyển khỏi mỗi trạng thái (có thể chuyển trở về chính nó). Một trạng thái, thường ký hiệu là q0, gọi là trạng thái bắt đầu (trạng thái ôtômát bắt đầu). Một số trạng thái được thiết kế như là các trạng thái kết thúc hay trạng thái chấp nhận. Một đồ thị có hướng, gọi là sơ đồ chuyển (transition diagram) tương ứng với một DFA như sau: các đỉnh của đồ thị là các trạng thái của DFA; nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a chuyển từ trạng thái q đến trạng thái p trong sơ đồ chuyển. DFA chấp nhận một chuỗi x nếu như tồn tại dãy các phép chuyển tương ứng trên mỗi ký hiệu của x dẫn từ trạng thái bắt đầu đến một trong những trạng thái kết thúc. Chẳng hạn, sơ đồ chuyển của một DFA được mô tả trong hình 3.1. Trạng thái khởi đầu q0 được chỉ bằng mũi tên có nhãn "Start". Chỉ có duy nhất một trạng thái kết thúc, cũng là q0 trong trường hợp này, được chỉ ra bằng hai vòng tròn. Ôtômát này chấp nhận tất cả các chuỗi số 0 và số 1 với số số 0 và số số 1 là số chẵn. Thí dụ 3.1 : Figure 3.1 Hình 3.1 - Sơ đồ chuyển của một DFA Một điều cần lưu ý, DFA sử dụng mỗi trạng thái của nó để giữ chỉ một phần của chuỗi số 0 và 1 chứ không phải chứa một số thực sự, vì thế DFA cần dùng một số hữu hạn trạng thái. Định nghĩa Một cách hình thức ta định nghĩa ôtômát hữu hạn là bộ gồm năm thành phần (Q, [U+F053], [U+F064], q0, F), trong đó : . Q là tập hợp hữu hạn các trạng thái.
15 . [U+F053] là bộ chữ cái nhập hữu hạn. . [U+F064] là hàm chuyển ánh xạ từ Q [U+F0B4] [U+F053] [U+F0AE] Q, tức là [U+F064](q, a) là một trạng thái được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a. . q0 [U+F0CE] Q là trạng thái bắt đầu .F [U+F0CD] Q là tập các trạng thái kết thúc. Ta vẽ DFA như là bộ điều khiển hữu hạn, với mỗi trạng thái thuộc Q, DFA đọc một chuỗi các ký hiệu a từ [U+F053] viết trên băng (như hình vẽ). Figure 3.2 Hình 3.2 - Mô tả một DFA Trong một lần chuyển, DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển sang trạng thái được xác định bởi hàm chuyển [U+F064](q, a), rồi dịch đầu đọc sang phải một ký tự. Nếu [U+F064](q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận chuỗi được viết trên băng input phía trước đầu đọc, nhưng không bao gồm ký tự tại vị trí đầu đọc vừa dịch chuyển đến. Trong trường hợp đầu đọc đã dịch đến cuối chuỗi trên băng, thì DFA mới chấp nhận toàn bộ chuỗi trên băng. Hàm chuyển trạng thái mở rộng Để có thể mô tả một cách hình thức hoạt động của một DFA trên chuỗi, ta mở rộng hàm chuyển [U+F064] để áp dụng đối với một trạng thái trên chuỗi hơn là một trạng thái trên từng ký hiệu. Ta định nghĩa hàm chuyển [U+F064] như một ánh xạ từ Q [U+F0B4] [U+F053]* [U+F0AE] Q với ý nghĩa [U+F064](q, w) là trạng thái DFA chuyển đến từ trạng thái q trên chuỗi w. Một cách hình thức, ta định nghĩa : 1. d (q, [U+F065]) = q 2. [U+F064] (q, wa) = [U+F064]([U+F064] (q, w), a), với mọi chuỗi w và ký hiệu nhập a. Một số quy ước về ký hiệu : • Q là tập các trạng thái. Ký hiệu q và p (có hoặc không có chỉ số) là các trạng thái, q0 là trạng thái bắt đầu. • [U+F053] là bộ chữ cái nhập. Ký hiệu a, b (có hoặc không có chỉ số) và các chữ số là các ký hiệu nhập. • [U+F064] là hàm chuyển. • F là tập các trạng thái kết thúc. • w, x, y và z (có hoặc không có chỉ số) là các chuỗi ký hiệu nhập. Ngôn ngữ được chấp nhận bởi DFA Một chuỗi w được chấp nhập bởi ôtômát hữu hạn M (Q, [U+F053], [U+F064], q0, F) nếu [U+F064](q0, w) = p với p [U+F0CE] F. Ngôn ngữ được chấp nhận bởi M, ký hiệu L(M) là tập hợp: L(M) = { w [U+F07C] [U+F064] (q0, w) [U+F0CE] F}
16 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Thí dụ 3.2 : Xét sơ đồ chuyển ở hình 3.1. Theo khái niệm hình thức, ta có DFA được xác định bởi M (Q, [U+F053], [U+F064], q0, F) với Q = {q0, q1, q2, q3}, [U+F053] = {0, 1}, F = {q0} và hàm chuyển [U+F064] như sau: d Inputs Trạng thái 0 1 q0 q2 q1 q1 q3 q0 q2 q0 q3 q3 q1 q2 Table 3.1 Giả sử chuỗi w = 110101 được nhập vào M. Ta có [U+F064](q0, 1) = q1 và [U+F064](q1, 1) = q0 ,vậy [U+F064](q0, 11) = [U+F064]([U+F064](q0,1),1) = [U+F064](q1, 1) = q0. Tiếp tục [U+F064](q0, 0) = q2, vậy [U+F064](q0, 110) = [U+F064]([U+F064](q0, 11), 0) = q2. Tiếp tục ta có [U+F064](q0, 1101) = q3, [U+F064](q0, 11010) = q1 Và cuối cùng [U+F064](q0, 110101) = q0 [U+F0CE] F. (Hay d(q0, 110101) = d(q1, 10101) = d(q0, 0101) = d(q2, 101) = d(q3, 01) = d(q1, 1) = q0 [U+F0CE] F) Vậy 110101 thuộc L(M). Ta có thể chứng minh rằng L(M) là tập mọi chuỗi có số chẵn số 0 và số chẵn số 1. Theo mô tả DFA như trên, ta thấy cũng có thể dùng bảng hàm chuyển (transition table) để mô tả các phép chuyển trạng thái của một ôtômát hữu hạn. Trong bảng hàm chuyển, hàng chứa các trạng thái thuộc tập trạng thái của ôtômát và cột là các ký hiệu thuộc bộ chữ cái nhập. Bảng hàm chuyển gợi ý cho chúng ta một cấu trúc dữ liệu để mô tả cho một ôtômát hữu hạn, đồng thời cũng cho thấy có thể dễ dàng mô phỏng hoạt động của DFA thông qua một chương trình máy tính, chẳng hạn dùng cấu trúc vòng lặp. Giải thuật mô phỏng hoạt động của một DFA . Input : Chuỗi nhập x kết thúc bởi $. Output : Câu trả lời "YES" nếu DFA chấp nhận chuỗi x và "NO" nếu ngược lại Giải thuật :q := q0 ;c := nextchar ; { c là ký hiệu nhập được đọc tiếp theo }While c $ dobeginq := d(q, c);c := nextchar ;endIf q in F then write ("YES") else write("NO"); Nhận xét : Một cách tổng quát, ta thấy tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu hạn. Mặt khác, hàm chuyển d là hàm toàn phần và đơn trị, cho nên các bước chuyển của ôtômát luôn luôn được xác định một cách duy nhất. Chính vì hai đặc điểm này mà DFA mô tả như trên được gọi là ôtômát hữu hạn đơn định. 3.1.2 Ôtômát hữu hạn không đơn định - NFA (Nondeterministic Finite Au- tomata) Xét một dạng sửa đổi mô hình DFA để chấp nhận không, một hoặc nhiều hơn một phép chuyển từ một trạng thái trên cùng một ký hiệu nhập. Mô hình mới này gọi là ôtômát hữu hạn không đơn định (NFA). Một chuỗi ký hiệu nhập a1 a2 an được chấp nhận bởi một NFA nếu có tồn tại một chuỗi các phép chuyển, tương ứng với chuỗi nhập, từ trạng thái bắt đầu đến trạng thái kết thúc. Chẳng hạn, chuỗi 01001 được chấp nhận bởi ôtômát trong hình dưới đây vì có chuỗi phép chuyển qua các trạng thái q0, q0, q0, q3, q4, q4 có nhãn tương ứng là 0, 1, 0, 0, 1. NFA này chấp nhận tất cả các chuỗi có hai số 0 liên tiếp hoặc hai số 1 liên tiếp. Thí dụ 3.3 :
17 Figure 3.3 Hình 3.3 - Sơ đồ chuyển của một NFA Chú ý rằng có thể xem ôtômát hữu hạn đơn định - DFA (hay gọi tắt là FA) là một trường hợp đặc biệt của NFA, trong đó mỗi trạng thái chỉ có duy nhất một phép chuyển trên mỗi ký hiệu nhập. Vì thế trong DFA, với một chuỗi nhập w và trạng thái q, chỉ có đúng một đường đi nhãn w bắt đầu từ q. Để xác định chuỗi w có được chấp nhận bởi DFA hay không chỉ cần kiểm tra đường đi này. Nhưng đối với NFA, có thể có nhiều đường đi có nhãn là w, và do đó tất cả phải được kiểm tra để thấy có hay không có đường đi tới trạng thái kết thúc. Tương tự như DFA, NFA cũng hoạt động với một bộ điều khiển hữu hạn đọc trên băng nhập. Tuy nhiên, tại mỗi thời điểm, bộ điều khiển có thể chứa một số bất kỳ trạng thái. Khi có sự lựa chọn trạng thái kế tiếp, chẳng hạn như từ trạng thái q0 trên ký hiệu nhập 0 ở hình 3.3, ta phải tưởng tượng như có các bản sao của ôtômát đang thực hiện đồng thời. Mỗi trạng thái kế tiếp mà ôtômát có thể chuyển đến sẽ tương ứng với một bản sao của ôtômát mà tại đó bộ điều khiển đang chứa trạng thái đó. Chẳng hạn, với chuỗi 01001, ta có :
18 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Figure 3.4 Định nghĩa Một cách hình thức ta định nghĩa ôtômát hữu hạn không đơn định NFA là một bộ 5 thành phần (Q, [U+F053], [U+F064], q0, F) trong đó Q, [U+F053], q0 và F có ý nghĩa như trong DFA, nhưng [U+F064] là hàm chuyển ánh xạ từ Q [U+F0B4] [U+F053] [U+F0AE] 2Q. Khái niệm [U+F064](q, a) là tập hợp tất cả các trạng thái p sao cho có phép chuyển trên nhãn a từ trạng thái q tới p. Hàm chuyển trạng thái mở rộng Để thuận tiện trong việc mô tả hoạt động ôtômát trên chuỗi, ta mở rộng hàm chuyển [U+F064] ánh xạ từ Q [U+F0B4] [U+F053]* [U+F0AE] 2Q như sau : 1. d(q, e) = {q} 1. [U+F064](q, wa) = { p [U+F07C] có một trạng thái r trong [U+F064](q, w) mà p thuộc [U+F064](r, a)} = [U+F064]([U+F064](q, w), a) 1. d(P, w) = Èq [U+F0CE] P d(q, w) , [U+F022]P [U+F0CD] Q. Ngôn ngữ được chấp nhận bởi NFA Ngôn ngữ L(M), với M là ôtômát hữu hạn không đơn định NFA (Q, [U+F053], [U+F064], q0, F) là tập hợp : L(M) = {w [U+F07C] [U+F064](q0, w) có chứa một trạng thái trong F } Thí dụ 3.4 : Xét sơ đồ chuyển của hình 3.3. Theo khái niệm hình thức, ta có : NFA M ({q0, q1, q2, q3, q4}, {0, 1}, d, q0, {q2, q4}) với hàm chuyển d như sau :
19 d Inputs Trạng thái 0 1 q0 {q0,q3} {q0,q1} q1 Æ {q2} q2 {q2} {q2} q3 {q4} Æ q4 {q4} {q4} Table 3.2 Xét chuỗi nhập w = 01001 Ta có :d (q0, 0) = {q0, q3} d (q0, 01) = d(d(q0, 0),1) = d({q0, q3},1) = d (q0, 1) È d (q3, 1) = {q0, q1} Tương tự , ta có thể tính : d (q0, 010) = {q0, q3} d (q0, 0100) = {q0, q3, q4} và d (q0, 01001) = {q0, q1, q4} Do q4 [U+F0CE] F nên w [U+F0CE] L (M). Câu hỏi : ? 1. Hãy cho nhận xét về điểm khác biệt quan trọng giữa DFA và NFA ? 2. Theo bạn, dạng đơn định hay không đơn định sẽ dùng nhận dạng một chuỗi dễ dàng hơn ? 3.1.3 Sự tương đương giữa DFA và NFA Vì mỗi DFA là một NFA, nên rõ ràng lớp ngôn ngữ được chấp nhận bởi NFA cũng bao gồm các tập chính quy (đây chính là ngôn ngữ được chấp nhận bởi DFA ). Tuy nhiên, không có cơ sở để nói rằng NFA chỉ chấp nhận duy nhất các tập hợp này. Điều đó cho thấy DFA có thể mô phỏng được hoạt động của NFA, nghĩa là với mỗi NFA, ta có thể xây dựng một DFA tương đương (chấp nhận cùng một ngôn ngữ với nó). Đặt một DFA mô phỏng hoạt động của NFA là cho phép các trạng thái của DFA tương ứng với tập các trạng thái của NFA. Tại mỗi thời điểm, DFA lưu giữ trong bộ điều khiển tất cả các trạng thái mà NFA có thể chuyển đến khi đọc cùng một input như DFA. ĐỊNH LÝ 3.1 : Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA chấp nhận L. Chứng minh Đặt M (Q, [U+F053], [U+F064], q0, F) là NFA chấp nhận L. Ta xây dựng DFA M’ (Q’, [U+F053], [U+F064]’, q0’, F’) tương đương như sau: - Các trạng thái của M’ là tất cả các tập hợp con của tập trạng thái của M, hay Q’= 2Q. Tại mỗi thời điểm, M’ sẽ lưu giữ trong trạng thái của nó tất cả các trạng thái có thể của M. Một phần tử trong Q’ được ký hiệu là [q1, q2, , qi], trong đó các trạng thái q1, q2, , qi [U+F0CE] Q. Ta xem [q1, q2, , qi] là một trạng thái đơn của DFA tương ứng với một tập trạng thái của NFA. - q0’ = [q0]. - F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc trong tập F của M. - Ta định nghĩa hàm chuyển [U+F064]’ như sau : d’ ([q1, q2, , qi], a) = [p1, p2, , pj] nếu và chỉ nếu [U+F064] ({q1, q2, , qi }, a) = {p1, p2, , pj} Bây giờ ta chứng minh quy nạp theo độ dài của chuỗi nhập x rằng: d’(q0’, x) = [q1, q2, , qi] Uˆ d(q0, x) = {q1, q2, , qi} (1)
20 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Với [U+F0BD]x[U+F0BD]= 0 , ta có x = [U+F065] và q0’ = [q0] nên (1) hiển nhiên đúng Giả sử (1) đúng với các chuỗi nhập có độ dài tới m. Xét chuỗi nhập có độ dài m + 1, đặt chuỗi này là xa với a [U+F0CE] [U+F053], ta có : d’(q0’, xa) = d’(d’(q0’, x), a) Theo định nghĩa : d’([p1, p2, , pi], a) = [r1, r2, , rk] Uˆ d({p1, p2, , pj}, a) = {r1, r2, , rk}. Mặt khác theo giả thiết quy nạp d’(q0’, x) = [p1, p2, , pj] Uˆ d(q0, x) = {p1, p2, , pj}, nên thay vào ta có : d’(q0’, xa) = [r1, r2, , rk] Uˆ d(q0, xa) = {r1, r2, , rk}. Dễ thấy rằng d’(q0’, x) [U+F0CE] F’ khi và chỉ khi d(q0, x) có chứa ít nhất một trạng thái [U+F0CE] F. Vậy L(M) = L(M’) Vì NFA và DFA chấp nhận cùng các tập hợp, nên ta sẽ không phân biệt chúng trừ khi điều đó thật sự cần thiết, sẽ đơn giản hơn để hiểu cả hai cùng là ôtômát đơn định. Thí dụ 3.5 : Cho NFA M ({q0, q1}, {0, 1}, d, q0, {q1}) với hàm chuyển d như sau : d(q0, 0) = {q0, q1},d(q0,1) = {q1},d(q1, 0) = [U+F0C6], d(q1, 1) = {q0, q1} Ta xây dựng DFA tương đương M’ (Q’, {0, 1}, d’, [q0], F’) chấp nhận L(M) như sau : . Q’ : chứa tất cả các tập con của {q0, q1}, vậy Q’ = {[q0], [q1], [q0, q1], [U+F0C6]} . Hàm chuyển d’ : Vì d(q0, 0) = {q0, q1} nên d’([q0], 0) = [q0, q1] Tương tự : d’([q0], 1) = [q1] d’([q1], 0) = [U+F0C6] d’([q1], 1) = [q0, q1] Mặt khác : d’([U+F0C6], 0) = d’([U+F0C6], 1) = [U+F0C6] Cuối cùng : d’([q0, q1],0) = [q0, q1] ( vì d({q0, q1},0) = d(q0, 0) [U+F0C8] d(q1, 0) = {q0, q1} [U+F0C8] [U+F0C6] = {q0, q1}) d’([q0, q1], 1) = [q0, q1] ( vì d({q0, q1},1) = d(q0, 1) [U+F0C8] d(q1, 1) = {q1} [U+F0C8] {q0, q1} = {q0, q1}) . Tập trạng thái kết thúc F’ = {[q1], [q0, q1]} Thực tế, có rất nhiều trạng thái của NFA không có hàm chuyển đến từ trạng thái bắt đầu [q0]. Do đó, thông thường, cách tốt nhất là ta nên xây dựng DFA tương đương bắt đầu từ trạng thái [q0] và thêm vào các trạng thái mới cho DFA chỉ khi có các hàm chuyển từ một trạng thái đã được thêm vào trước đó. Câu hỏi : ? Bạn có nhận xét gì về kích thước giữa một DFA và một NFA tương đương với nó chấp nhận cùng một tập ngôn ngữ ? 3.1.4 NFA với [U+F065]-dịch chuyển (NFA[U+F065]) Ta mở rộng mô hình NFA cho phép các phép chuyển trên nhãn rỗng [U+F065]. Sơ đồ chuyển sau đây của một NFA chấp nhận chuỗi gồm một số bất kỳ (có thể là 0) chữ số 0 sau đó là một số bất kỳ chữ số 1 và sau nữa là một số bất kỳ chữ số 2. Thông thường, ta nói NFA chấp nhận một chuỗi w nếu có đường truyền nhãn w từ trạng thái bắt đầu đến một trạng thái kết thúc. Chẳng hạn, chuỗi 002 được chấp nhận bởi đường truyền q0, q0, q0, q1, q2, q2 với các cung nhãn 0, 0, [U+F065], [U+F065], 2. Thí dụ 3.6 : Sơ đồ chuyển của một NFA với [U+F065]-dịch chuyển :
21 Figure 3.5 Hình 3.4 - NFA với [U+F065]-dịch chuyển Định nghĩa: Một cách hình thức ta định nghĩa NFA với [U+F065]-dịch chuyển là bộ 5 thành phần (Q, [U+F053], [U+F064], q0, F) với tất cả các thành phần có ý nghĩa như trên, nhưng hàm chuyển [U+F064] là ánh xạ từ Q [U+F0B4] ([U+F053] [U+F0C8] {[U+F065]}) [U+F0AE] 2Q. Khái niệm [U+F064](q, a) gồm tất cả các trạng thái p sao cho có phép chuyển nhãn a từ q tới p, trong đó a là một ký hiệu thuộc [U+F053] hoặc là [U+F065]. Hàm chuyển trạng thái mở rộng: Ta mở rộng hàm chuyển [U+F064] thành hàm chuyển [U+F064]* ánh xạ từ Q [U+F0B4] [U+F053]* [U+F0AE] 2Q. [U+F064]*(q,w) chứa tất cả các trạng thái p sao cho có thể đi từ q tới p theo đường đi nhãn w (có thể chứa cạnh nhãn [U+F065]). Ta sử dụng [U+F065]-CLOSURE(q) để xác định tập tất cả các đỉnh p sao cho có đường đi từ q tới p với nhãn [U+F065]. Thí dụ 3.7 : Trong hình 3.4, [U+F065]-CLOSURE(q0) = {q0, q1, q2}. Vì đường đi chỉ có một đỉnh q0 (không có cung trên đường đi) là đường đi từ q0 tới q0 có tất cả các cạnh nhãn là [U+F065]. Đường đi q0, q1 chỉ ra rằng q1 thuộc [U+F065]-CLOSURE(q0). Và đường đi q0, q1, q2 chỉ ra rằng q2 thuộc [U+F065]-CLOSURE(q0). Đặt [U+F065]-CLOSURE(P) = [U+F0C8]q[U+F0CE]P [U+F065]-CLOSURE(q), trong đó P là một tập các trạng thái và q là một trạng thái. Ta định nghĩa hàm [U+F064]* như sau: 1. [U+F064]*(q, e) = e-CLOSURE(q) 2. [U+F064]*(q, wa) = e-CLOSURE(P), trong đó tập P = {p [U+F07C] có r trong [U+F064]*(q, w) sao cho p [U+F0CE] [U+F064](r, a)}, [U+F022]w [U+F0CE] [U+F053]* và a [U+F0CE] [U+F053] Hay [U+F064]*(q, wa) = e-CLOSURE(d([U+F064]*(q, w), a) Ta mở rộng [U+F064] và [U+F064]* trên tập hợp các trạng thái R như sau : 3. [U+F064] (R, a) = È q[U+F0CE]R [U+F064](q, a), và 4. [U+F064]*(R, w) = Èq[U+F0CE]R [U+F064]*(q, w) Câu hỏi : ? Hãy so sánh sự khác biệt giữa hàm chuyển [U+F064] và [U+F064]*? Nhận xét : [U+F064]*(q, a) và [U+F064](q, a) không nhất thiết bằng nhau vì [U+F064]*(q, a) gồm tất cả các trạng thái có thể chuyển đến được từ q trên nhãn a gồm cả đường đi nhãn e, trong khi đó d(q, a) chỉ gồm các trạng thái có thể đến được từ q chỉ bằng các cung nhãn a. Tương tự [U+F064]*(q, e) có thể cũng không bằng [U+F064](q, e). Vì vậy ta phải phân biệt ký hiệu [U+F064] và [U+F064]* đối với NFA với e-dịch chuyển. Ngôn ngữ được chấp nhận bởi NFA[U+F065]: Ta định nghĩa L(M), ngôn ngữ được chấp nhận bởi NFA[U+F065] M = (Q, [U+F053], [U+F064], q0, F) là tập hợp các chuỗi : L(M) = {w [U+F07C] [U+F064]*(q0, w) có chứa ít nhất một trạng thái trong F} Thí dụ 3.8 : Xét sơ đồ chuyển của hình 3.4.
22 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Theo khái niệm hình thức, ta có NFA M ({q0, q1, q2}, {0, 1, 2}, [U+F064], q0, {q2}) với hàm chuyển [U+F064] như sau : d Inputs Trạng thái 0 1 2 e q0 {q0 } Æ Æ { q1} q1 Æ {q1} Æ {q1} q2 Æ Æ {q2} Æ Table 3.3 Xét chuỗi nhập w = 012. Ta cần tính [U+F064]*(q0, 012) Ta có : [U+F064]*(q0, e) = e-CLOSURE(q0) = {q0, q1, q2} vậy [U+F064]*(q0, 0) = e-CLOSURE([U+F064]([U+F064]*(q0, e), 0) = e-CLOSURE(d({q0, q1, q2}, 0)) = e-CLOSURE(d(q0, 0) È d(q1, 0) È d(q2, 0)) = e-CLOSURE({q0} È Æ È Æ ) = e-CLOSURE({q0}) = {q0, q1, q2} và [U+F064]*(q0, 01) = e-CLOSURE([U+F064]([U+F064]*(q0, 0), 1)) = e-CLOSURE(d({q0, q1, q2}, 1)) = e-CLOSURE(d(q0, 1) È d(q1, 1) È d(q2, 1)) = e-CLOSURE(Æ È {q1} ÈÆ ) = e-CLOSURE({q1}) = {q1, q2} [U+F0DE] [U+F064]*(q0, 012) = e-CLOSURE(d( [U+F064]*(q0, 01), 2)) = e-CLOSURE(d({q1, q2}, 2)) = e-CLOSURE(d(q1, 2) È d(q2, 2)) = e-CLOSURE(Æ È {q2}) = e-CLOSURE({q2}) = {q2} Do [U+F064]*(q0, 012) có chứa trạng thái q2 [U+F0CE] F nên chuỗi w [U+F0CE] L(M). Giải thuật mô phỏng hoạt động của một NFA[U+F065] : . Input : Chuỗi nhập x được kết thúc bởi $. . Output : Câu trả lời "YES" nếu NFA chấp nhận chuỗi x và "NO" nếu ngược lại. . Giải thuật : q := e-CLOSURE(q0); c := nextchar ; { c là ký hiệu nhập được đọc tiếp theo } While c <> $ do begin q := e-CLOSURE(d(q, c)); c := nextchar ; end If q in F then write ("YES") else write ("NO"); 3.1.5 Sự tương đương giữa NFA có và không có e-dịch chuyển Tương tự như NFA, khả năng có thể thực hiện phép chuyển trên nhãn e của NFAe cũng không làm cho NFAe chấp nhận được các tập hợp không chính quy. Ta có thể dẫn chứng điều này bằng cách mô phỏng hoạt động của một NFAe bởi một NFA không có e-dịch chuyển.
23 ĐỊNH LÝ 3.2 : Nếu L được chấp nhận bởi một NFA có e-dịch chuyển thì L cũng được chấp nhận bởi một NFA không có e-dịch chuyển. Chứng minh Đặt M (Q, [U+F053], [U+F064], q0, F) là NFA với e-dịch chuyển. Ta xây dựng NFA M’(Q, [U+F053], [U+F064]’, q0, F’) tương đương không có e-dịch chuyển, trong đó: F [U+F0C8] {q0} nếu e-CLOSURE(q0) chứa một trạng thái thuộc F . F’ = F trong các trường hợp còn lại . [U+F064]’(q, a) là [U+F064]*(q, a) với q [U+F0CE] Q và a [U+F0CE] [U+F053]. Chú ý rằng M’ không có e-dịch chuyển nên ta có thể dùng [U+F064]’ thay cho [U+F064]*’, nhưng phải phân biệt [U+F064] và [U+F064]*. Ta chứng minh bằng quy nạp trên [U+F07C] x [U+F07C] rằng [U+F064]’(q0, x) = [U+F064] *(q0, x). Tuy nhiên, điều đó có thể không đúng với x = e vì [U+F064]’(q0, e) = {q0} trong khi [U+F064] *(q0, e) = e-CLOSURE(q0). Do đó, cơ sở quy nạp bắt đầu với độ dài chuỗi là 1. Với | x | = 1 thì x là một ký hiệu a và [U+F064]’(q, a) = [U+F064] *(q, a) theo định nghĩa [U+F064]’. Xét | x | > 1: đặt x = wa với a là một ký hiệu trong [U+F053]. Ta có [U+F064]’(q, wa) = [U+F064]’([U+F064]’(q0, w), a) Theo giả thiết quy nạp thì [U+F064]’(q0, w) = [U+F064] *(q0, w). Đặt [U+F064] *(q0, w) = P, ta cần chỉ ra rằng [U+F064](P, a) = [U+F064] *(q0, wa). Ta có [U+F064]’(P, a) = Èq[U+F0CE]P [U+F064]’(q, a) = Èq[U+F0CE]P [U+F064] *(q, a). Hơn nữa vì P = [U+F064] *(q0, w) nên Èq[U+F0CE]P [U+F064] *(q, a) = [U+F064] *(q0, wa) ( theo quy tắc 2 trong định nghĩa [U+F064] *). Vậy [U+F064]’(q0, wa) = [U+F064] *(q0, wa) Để đầy đủ chứng minh ta còn phải chỉ ra rằng [U+F064]’(q0, x) chứa một trạng thái trong F’ nếu và chỉ nếu [U+F064] *(q0, x) chứa một trạng thái trong F. Nếu x = e thì điều đó hiển nhiên đúng (theo định nghĩa của F’) Nếu x [U+F0B9] e thì ta đặt x = wa với a [U+F0CE] [U+F053]. Nếu [U+F064] *(q0, x) chứa một trạng thái trong F thì chắc chắn [U+F064]’(q0, x) chứa cùng trạng thái trong F’. Ngược lại, nếu [U+F064]’(q0, x) chứa một trạng thái trong F’ khác hơn q0 thì [U+F064](q0, x) phải chứa một trạng thái trong F (vì tập F và F’ chỉ chênh lệch nhau trạng thái q0). Nếu [U+F064]’(q0, x) có chứa trạng thái q0 và q0 cũng là một trạng thái thuộc tập trạng thái kết thúc F thì vì [U+F064] *(q0, x) = e-CLOSURE([U+F064]([U+F064] *(q0, w),a)), nên trạng thái chung trong e-CLOSURE(q0) và trong F phải ở trong [U+F064] *(q0, x). Thí dụ 3.9 : Chuyển NFA với e-dịch chuyển ở hình 3.4 sang dạng NFA không có chứa e-dịch chuyển. Ta xây dựng NFA tương đương M’(Q, [U+F053], [U+F064]’, q0, F’) chấp nhận L(M) với các thành phần : . Q = {q0, q1, q2} . ˚a= {0, 1, 2} . Trạng thái bắt đầu : q0 . F’ = {q0, q2} do e-CLOSURE(q0) = {q0, q1, q2} có chứa q2 [U+F0CE] F . Hàm chuyển [U+F064]’ của M’ được xác định theo công thức : d’(q, a) = d*(q, a) = e-CLOSURE(d(d*(q0, e), a) Kết quả được chỉ ra trong bảng hàm chuyển sau : d’ Inputs Trạng thái 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} q1 Æ {q1, q2} {q2} q2 Æ Æ {q2}
24 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Table 3.4 Sơ đồ chuyển trạng thái: Figure 3.6 Hình 3.5 - NFA tương đương cho thí dụ 3.9 3.1.6 Giải thuật xây dựng DFA từ NFA Qua khảo sát các dạng mở rộng từ mô hình ôtômát hữu hạn ban đầu, ta thấy DFA thực chất là một trường hợp đặc biệt của NFA, nhưng : - Nó không có sự truyền rỗng (truyền trên nhãn e) - Với mỗi trạng thái q và ký hiệu nhập a, chỉ có duy nhất một đường truyền đến một trạng thái khác. Giả sử mỗi trạng thái của DFA là một tập trạng thái của NFA, DFA dùng trạng thái của mình để lưu giữ tất cả các trạng thái của NFA đạt được sau khi NFA đọc một ký tự nhập. Như vậy sau khi đọc các ký tự nhập a1, a2, , an, DFA ở trạng thái là tập con của các trạng thái thuộc NFA, đạt được khi NFA đi từ trạng thái bắt đầu theo một con đường nào đó có tên a1a2 an. Số trạng thái của DFA lúc đó phải bằng số phần tử trong tập lũy thừa của số trạng thái NFA. Song, trên thực tế trường hợp xấu nhất này ít khi xảy ra. Các trạng thái thực sự được dùng trong sơ đồ chuyển cho một DFA sẽ được xác định theo các phép chuyển trạng thái trên nhãn là mọi ký hiệu từ trạng thái bắt đẩu của DFA, và sau đó lần lượt được bổ sung thêm vào tập trạng thái nếu như nó chưa có trong đó. Giải thuật chi tiết được trình bày như sau : Input: Một ôtômát hữu hạn không đơn định NFA. Output: Một ôtômát hữu hạn đơn định DFA nhận dạng cùng ngôn ngữ như NFA. Phương pháp: Xây dựng bảng hàm chuyển cho DFA mô phỏng đồng thời tất cả các chuyển dịch của NFA trên chuỗi nhập cho trước. Ta dùng các tác vụ sau để lưu giữ các tập trạng thái của NFA : (q : là một trạng thái của NFA, T : là tập trạng thái của NFA) a) e-closure(q) : là tập trạng thái của NFA đạt được từ trạng thái q trên sự truyền rỗng. b) e-closure(T) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q thuộc tập T trên sự truyền rỗng. c) d(T, a) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q thuộc tập T trên sự truyền bằng ký hiệu a. Phân tích: Trước khi đọc vào một ký tự nhập, DFA có thể ở một trạng thái bất kỳ trong các trạng thái thuộc e-closure(q0) với q0 là trạng thái bắt đầu của NFA. Gọi trạng thái này là T. Giả sử các trạng thái của T là các trạng thái đạt được từ q0 trên các ký hiệu nhập và giả sử a là ký hiệu nhập kế tiếp. Khi đọc a, NFA có
25 thể chuyển đến một trạng thái bất kỳ trong tập trạng thái d(T, a). Khi chúng ta cho phép sự truyền rỗng, NFA có thể ở bất kỳ trạng thái nào trong e-closure(d(T, a)) sau khi đã đọc a. Giải thuật : Trạng thái bắt đầu [U+F065]-closure(q0) chỉ là một trạng thái trong các trạng thái của DFA và trạng thái này chưa được đánh dấu; While Có một trạng thái T của DFA chưa được đánh dấu do Begin Đánh dấu T; { xét trạng thái T} For Với mỗi ký hiệu nhập a do begin U:= [U+F065]-closure([U+F064](T, a)) If U không có trong tập trạng thái của DFA then begin Thêm U vào tập các trạng thái của DFA và trạng thái này chưa được đánh dấu; [U+F064][T, a] := U; {[U+F064][T, a] là phần tử của bảng chuyển DFA}end; end; End; Ta xây dựng các trạng thái và bảng hàm chuyển cho DFA theo cách như sau : - Mỗi trạng thái của DFA tượng trưng bởi một tập trạng thái của NFA mà NFA có thể chuyển đến sau khi đọc một chuỗi ký hiệu nhập gồm: tất cả sự truyền rỗng có thể xảy ra trước hoặc sau các ký hiệu được đọc. - Trạng thái bắt đầu của DFA là e-closure(q0) - Các trạng thái và hàm chuyển sẽ được thêm vào D bằng giải thuật trên. - Một trạng thái của DFA là trạng thái kết thúc nếu nó là tập các trạng thái của NFA chứa ít nhất một trạng thái kết thúc của NFA. Việc tính toán e-closure(T) có thể xem như quá trình tìm kiếm một đồ thị của các nút từ các nút cho trước và đồ thị bao gồm toàn những cạnh có nhãn e của NFA. Giải thuật đơn giản để tìm e-closure(T) là dùng Stack để lưu giữ các trạng thái mà cạnh của chúng chưa được kiểm tra cho sự truyền rỗng. Thí dụ 3.10 : Tạo DFA từ NFAe sau Figure 3.7 Hình 3.6 – Thí dụ chuyển NFA có [U+F065]-dịch chuyển Các bước xây dựng tập trạng thái cho DFA :
26 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY 1. Trạng thái bắt đầu của DFA : [U+F065]-closure(0) = {0, 1, 2, 4, 7} = A* 2. [U+F065]-closure([U+F064](A, a)) = [U+F065]-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B* 3. [U+F065]-closure([U+F064](A, b)) = [U+F065]-closure({5}) = {1, 2, 4, 5, 6, 7} = C* 4. [U+F065]-closure([U+F064](B, a)) = [U+F065]-closure({3, 8}) = B 5. [U+F065]-closure([U+F064](B, b)) = [U+F065]-closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9} = D* 6. [U+F065]-closure([U+F064](C, a)) = [U+F065]-closure({3, 8}) = B 7. [U+F065]-closure([U+F064](C, b)) = [U+F065]-closure({5}) = C 8. [U+F065]-closure([U+F064](D, a)) = [U+F065]-closure({3, 8}) = B 9. [U+F065]-closure([U+F064](D, b)) = [U+F065]-closure({5, 10}) = {1, 2, 4, 5, 6, 7, 10} = E* 10. [U+F065]-closure([U+F064](E, a)) = [U+F065]-closure({3, 8}) = B 11. [U+F065]-closure([U+F064](E, b)) = [U+F065]-closure({5}) = C Từ các tập trạng thái này, ta xác định được A là trạng thái bắt đầu, E là trạng thái kết thúc (vì trong E có chứa trạng thái 10 là trạng thái kết thúc của NFA) và bảng hàm chuyển của DFA như sau : Trạng thái Ký hiệu nhập a b A B C B B D C B C D B E E B C Table 3.5 Từ bảng hàm chuyển như trên, ta xây dựng sơ đồ chuyển trạng thái cho DFA tương đương nhận dạng cùng ngôn ngữ có dạng như sau : Figure 3.8 Hình 3.7 – DFA tương đương cho thí dụ 3.10 Nhận xét : Mặc dù có sự khác nhau trong định nghĩa, ta thấy dạng không đơn định NFA được định nghĩa tổng quát hơn dạng đơn định DFA, nhưng rõ ràng khả năng nhận dạng cùng lớp ngôn ngữ của chúng
27 là tương đương nhau. Trong thực tế, các máy tính số hoàn toàn là đơn định, trạng thái của chúng tại mỗi thời điểm là xác định được duy nhất từ một chuỗi nhập bất kỳ và trạng thái bắt đầu. Câu hỏi : ? Tại sao cần định nghĩa dạng không đơn định ? Một số gợi ý câu trả lời: 1. Trong một số các bài toán mang tính chọn lựa, có nhiều hướng giải quyết (nhiều cách đi) như trong các chương trình trò chơi (games) thì thông thường hướng giải quyết tốt nhất (cách đi tốt nhất) là không biết trước được, nhưng có thể tìm thấy được bằng cách sử dụng chiến lược tìm kiếm quay lui (back-tracking). Khi có một vài khả năng chọn lựa có thể, ta chọn một khả năng trong chúng và đi theo hướng đó cho đến khi xác định hướng đó là tốt nhất hay chưa. Nếu chưa phải là hướng tốt nhất, ta phải quay về điểm quyết định cuối cùng trước đó và thử khảo sát theo một hướng khác. Một giải thuật mô phỏng quá trình tìm kiếm quay lui này là một giải thuật không đơn định. 2. Không đơn định đôi khi còn rất hữu hiệu trong việc giúp giải quyết các bài toán dễ dàng. Chẳng hạn, trong một số bài toán thì việc xây dựng một NFA có vẻ tự nhiên và đơn giản hơn việc tìm một DFA cho chúng. Tương tự như vậy, không đơn định còn là một cơ chế hiệu quả dùng mô tả văn phạm sinh ra ngôn ngữ một cách súc tích (sự chọn lựa các luật sinh sinh từ cùng một biến). 3. Trong thực tế, một vài kết quả là dễ dàng được chứng minh đối với NFA hơn là DFA. Vì vậy việc cho phép cơ chế không đơn định thường làm đơn giản hóa các lý luận hình thức mà không ảnh hưởng đến tính tổng quát của kết luận. 3.2 BIỂU THỨC CHÍNH QUY (RE : Regular Expressions) Lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn cũng có thể được mô tả thông qua một dạng biểu thức ngắn gọn và súc tích gọi là biểu thức chính quy. Trong phần này, chúng ta sẽ giới thiệu sự kết hợp của các phép toán hợp, nối kết và bao đóng Kleene trên các tập hợp chuỗi để định nghĩa biểu thức chính quy và chứng tỏ rằng lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn thì thực sự là lớp ngôn ngữ được mô tả bởi biểu thức chính quy. 3.2.1 Định nghĩa Cho [U+F053] là một bộ chữ cái. Biểu thức chính quy trên [U+F053] và các tập hợp mà chúng mô tả được định nghĩa một cách đệ quy như sau: 1) [U+F0C6] là biểu thức chính quy ký hiệu cho tập rỗng 2) [U+F065] là biểu thức chính quy ký hiệu cho tập {[U+F065]} 3) [U+F022]a [U+F0CE] [U+F053], a là biểu thức chính quy ký hiệu cho tập {a} 4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs) và ( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R [U+F0C8] S, RS, R* tương ứng. Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lưu ý rằng thứ tự ưu tiên của các phép toán xếp theo thứ tự giảm dần là: phép bao đóng, phép nối kết, phép hợp. Chẳng hạn : Biểu thức ((0(1*)) + 1) có thể viết là 01*+ 1. Câu hỏi : ? Như trên ta nói, biểu thức chính quy dùng ký hiệu cho một lớp ngôn ngữ. Bạn hãy thử liệt kê một vài chuỗi và hình dung lớp ngôn ngữ được ký hiệu bởi biểu thức chính quy r = 01*+ 1 trên ? Phép toán bao đóng dương cũng có thể được sử dụng khi viết biểu thức chính quy. Ta có thể viết rút gọn rr* hay r*r thành r+. Nếu cần thiết phân biệt thì ta sẽ dùng ký hiệu r cho biểu thức chính quy r và L(r) cho ngôn ngữ được ký hiệu bởi biểu thức chính quy r; ngược lại một cách tổng quát, ta có thể dùng r cho cả hai.
28 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Thí dụ 3.11 : Một số biểu thức chính quy ký hiệu cho các ngôn ngữ : . 00 là biểu thức chính quy biểu diễn tập {00}. . (0+1)* ký hiệu cho tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng = {e, 0, 1, 00, 01, 10, 11, 010, 011, 0010 } . (0+1)*00(0+1)* ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp. = {00, 000, 100, 0000, 0001, 1000, 1001, 011001, } . (1+10)* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số 0 liên tiếp = {e, 1, 10, 11, 1010, 111, 101010, } . (0+[U+F065])(1+10)* ký hiệu cho tất cả các chuỗi không có hai số 0 liên tiếp. = {e, 0, 01, 010, 1, 10, 01010, 0111, } . (0+1)*011 ký hiệu cho tất cả các chuỗi 0, 1 tận cùng bởi 011. = {011, 0011, 1011, 00011, 11011, } . 0*1*2* ký hiệu cho tất cả các chuỗi có một số bất kỳ các số 0, theo sau là một số bất kỳ số 1 và sau nữa là một số bất kỳ số 2. = {e, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, } . 00*11*22* ký hiệu cho tất cả các chuỗi trong tập 0*1*2* với ít nhất một trong mỗi ký hiệu. 00*11*22* có thể được viết gọn thành 0+1+2+ Thí dụ 3.12 : Biểu thức chính quy ký hiệu cho tập hợp các chuỗi tên biến đúng trong ngôn ngữ lập trình Pascal : Một chuỗi tên biến (identifiers) được gọi là hợp lệ trong một chương trình Pascal nếu như nó bắt đầu bằng ít nhất một chữ cái và theo sau đó là các chữ cái, số, ký hiệu underline hoặc một vài ký hiệu cho phép khác trên bàn phím máy tính. Biểu thức chính quy có dạng như sau : r = (A + + Z + a + + z) (A + + Z + a + + z + 0 + + 9 + _ + )* Thí dụ 3.13 : Biểu thức chính quy ký hiệu cho tập hợp các số nguyên trong ngôn ngữ lập trình Pascal : Một chuỗi số nguyên trong một chương trình Pascal có thể bắt đầu bằng dấu âm (-) hoặc dấu dương (+) hay không chứa ký hiệu dấu, và theo sau đó là một chuỗi các ký hiệu số với ít nhất là một số. Biểu thức chính quy có dạng như sau : r = ( ‘+’ + ‘-‘ + [U+F065]) ( 0 + + 9 (0 + +9 )* Nhận xét : Thông thường, việc tìm một biểu thức chính quy ký hiệu cho một ngôn ngữ khó hơn việc xác định ngôn ngữ được ký hiệu bởi một biểu thức chính quy vì không có giải thuật cho loại bài toán này. 3.2.2 Một số tính chất đại số của biểu thức chính quy Dễ dàng chứng minh rằng, nếu cho r, s, t là các biểu thức chính quy thì ta có các đẳng thức sau : 1.r + s = s + r2. r + r = r 3.r + (s+t) = (r+s) + t4. r (st) = (rs) t 5. r (s+t) = rs + rt6. (r+s) t = rt + st 7. r[U+F065] = [U+F065] r = r8. [U+F0C6]r = r[U+F0C6] = [U+F0C6] 9. r + [U+F0C6] = r10.[U+F0C6]* = [U+F0C6] 11. ([U+F065] + r)* = r*12.r + r* = r* 13. ( r* )* = r*14. ( r* s* )* = (r+s)* Trong đó, ta có r = s có nghĩa là L(r) = L(s). 3.3 SỰ TƯƠNG ĐƯƠNG GIỮA ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Như trên đã nói, các ngôn ngữ được chấp nhận bởi ôtômát hữu hạn cũng là các ngôn ngữ được mô tả bởi biểu thức chính quy. Chính vì sự tương đương này, mà người ta gọi ngôn ngữ chấp nhận bởi ôtômát hữu hạn là các tập chính quy. Trong phần này, thông qua hai định lý, ta sẽ chỉ ra bằng quy nạp theo kích thước
29 của (số phép toán trong) biểu thức chính quy rằng có tồn tại một NFA với e-dịch chuyển chấp nhận cùng ngôn ngữ; đồng thời với mỗi DFA cũng có một biểu thức chính quy xác định chính ngôn ngữ của nó. ĐỊNH LÝ 3.3: Nếu r là biểu thức chính quy thì tồn tại một NFA với e-dịch chuyển chấp nhận L(r). Chứng minh Ta sẽ chứng minh quy nạp theo số phép toán của biểu thức chính quy r rằng có tồn tại một NFA M với e-dịch chuyển có một trạng thái kết thúc và không có các phép chuyển khỏi trạng thái này chấp nhận biểu thức chính quy r: L(M) = L(r). . r không có phép toán: Vậy r phải là [U+F0C6], e hoặc a (với a [U+F0CE] [U+F053]). Các NFA dưới đây thoả mãn điều kiện: Figure 3.9 Hình 3.7 - Các NFAe cho các kết hợp đơn . r có chứa các phép toán: Giả sử định lý đúng với r có ít hơn i phép toán, i [U+F0B3] 1. Xét r có i phép toán. Có 3 trường hợp : 1) r = r1+ r2. Cả hai biểu thức chính quy r1, r2 có ít hơn i phép toán, vậy ta có 2 ôtômát hữu hạn NFA M1 (Q1, [U+F053]1, [U+F064]1, q1, {f1}) và M2 (Q2, [U+F053]2, [U+F064]2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2). Vì các trạng thái có thể thay đổi tên nên ta giả sử hai tập trạng thái Q1 và Q2 là rời nhau. Đặt q0 là trạng thái bắt đầu mới và {f0} là tập trạng thái kết thúc mới, ta xây dựng NFA M (Q1 [U+F0C8] Q2 [U+F0C8] {q0, f0}, [U+F053]1 [U+F0C8] [U+F053]2, [U+F064], q0, {f0}), trong đó [U+F064] được xác định như sau: . d(q0, e) = {q1, q2} . d(q, a) = d1(q, a) với q [U+F0CE] Q1 - {f1} và a [U+F0CE] [U+F053]1 [U+F0C8] {[U+F065]} . d(q, a) = d2(q, a) với q [U+F0CE] Q2 - {f2} và a [U+F0CE] [U+F053]2 [U+F0C8] {[U+F065]} . d(f1, e) = d(f2, e) = {f0} Chú ý do giả thiết quy nạp là không có phép chuyển nào ra khỏi f1, f2 trong M1, M2. Vì vậy tất cả các phép chuyển của M1 và M2 đều có trong M. Cách xây dựng M chỉ ra trong hình a. Bất kỳ đường đi nào trong sơ đồ chuyển của M từ q0 tới f0 phải bắt đầu bằng cách đi tới q1 hoặc q2 bằng nhãn [U+F065]. Nếu đường đi qua q1 thì nó theo một đường đi nào đó trong M1 tới f1 rồi sau đó tới f0 bằng nhãn [U+F065]. Tương tự trong trường hợp đường đi qua q2. Có một đưòng đi từ q0 đến f0 nhãn x khi và chỉ khi có đường đi nhãn x trong M1 từ q1 đến f1 hoặc có đường đi nhãn x trong M2 từ q2 đến f2. Vậy L(M) = L(M1) [U+F0C8] L(M2)
30 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Figure 3.10 Hình a - Phép hợp Figure 3.11 Hình b - Phép nối kết Figure 3.12 Hình c - Phép bao đóng Hình 3.8 - Các NFAe cho kết hợp phức 2) r = r1 r2 Đặt M1 và M2 là các ôtômát NFA như trong trường hợp trên và ta xây dựng ôtômát M (Q, [U+F053] , [U+F064], {q1}, {f2}), trong đó [U+F064] được xác định như sau:
31 . [U+F064](q, a) = [U+F064]1(q, a) với q [U+F0CE] Q1 - {f1} và a [U+F0CE] [U+F053]1 [U+F0C8] {[U+F065]} . d(f1, e) = {q2} . [U+F064](q, a) = [U+F064]2(q, a) với q [U+F0CE] Q2 và a [U+F0CE] [U+F053]2 [U+F0C8] {[U+F065]} Cách xây dựng M chỉ ra trong hình b. Mỗi đường đi trong M từ q1 tới f2 là đường đi có nhãn x từ q1 tới f1 sau đó là một cung từ f1 tới q2 nhãn [U+F065] và tiếp đến là đường đi từ q2 tới f2. Vậy L(M) = {xy [U+F07C] x [U+F0CE] L(M1) và y [U+F0CE] L(M2)} hay L(M) = L(M1) L(M2). 3) r = r* Đặt M1 (Q1, [U+F053]1, [U+F064]1, q1, {f1}) và L(M1) = r1. Xây dựng M (Q1[U+F0C8] {q0, f0} [U+F053]1, [U+F064], q0, {f0}), trong đó [U+F064] được cho: . d(q0, e) = d(f1, e) = {q1, f0} . d(q, a) = d1(q, a) với q [U+F0CE] Q1 - {f1} và a [U+F0CE] [U+F053]1 [U+F0C8] {[U+F065]} Cách xây dựng M được chỉ ra trong hình c. Mỗi đường đi từ q0 tới f0 gồm: hoặc đường đi từ q0 tới f0 bằng nhãn [U+F065]; hoặc đường đi từ q0 tới q1 bằng nhãn [U+F065] và sau đó là đường đi từ q1 tới f1 trên chuỗi thuộc L(M), rồi đến f0 bằng nhãn [U+F065]. Như vậy có đường đi từ q0 tới f0 nhãn là x nếu và chỉ nếu ta có thể viết x = x1 x2 xj với j [U+F0B3] 0 (trường hợp j = 0 khi x = [U+F065]) [U+F022]xi [U+F0CE] L(M1). Vậy L(M) = L(M1)*. Thí dụ 3.14 : Xây dựng NFA[U+F065] chấp nhận lớp ngôn ngữ được ký hiệu bởi biểu thức chính quy r = 01* + 1. Ta thấy L(r) = { 1, 0, 01, 011, 0111, 01111, 011111, } là tập ngôn ngữ chứa các bit đơn 0, 1 và các chuỗi bit nhị phân bắt đầu bằng bit 0, theo sau là một chuỗi bit 1 với độ dài tuỳ ý. Theo quy luật thứ tự ưu tiên, biểu thức 01* + 1 thực chất là (0(1*)) + 1, vì vậy nó có dạng r1 + r2 với r1 = 01* và r2 = 1. Ta sẽ lần lượt xây dựng các NFA cho các biểu thức chính quy con, sau đó dựa vào các quy tắc kết hợp để xây dựng NFA cho toàn bộ biểu thức chính quy đã cho. . NFA cho r2 = 1 dễ dàng để xây dựng : Figure 3.13 . NFA cho r1 = 01*: Ta tách r1 = r3 r4 , trong đó r3 = 0 và r4 = 1* + NFA cho r3 = 0 : Figure 3.14
32 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY + NFA r4 = 1* : Ta viết r4 = r5*, trong đó r5 = 1. NFA cho r5 = 1 : Figure 3.15 Theo quy tắc 3) ta xây dựng được NFA cho r4 = r5* = 1* như sau : Figure 3.16 Theo quy tắc 2) ta xây dựng được NFA cho r1 = r3 r4 = 01* như sau : Figure 3.17 Cuối cùng, theo quy tắc 1) ta xây dựng NFA cho r = r1 + r2 = 01*+ 1 như sau :
33 Hình 3.9 - NFAe cho ví dụ 3.13 Phần chứng minh của Định lý 3.3 trên cũng chính là cơ sở của giải thuật chuyển đổi một biểu thức chính quy thành ôtômát hữu hạn. Một điểm cần lưu ý là thứ tự ưu tiên của các phép toán được sử dụng trong biểu thức chính quy, điều này rất quan trọng cho quá trình tách biểu thức chính quy thành các biểu thức con trong những trường hợp viết biểu thức chính quy ở dạng tắt (không có dấu ngoặc). Bây giờ, ta cần chứng tỏ rằng mọi tập hợp được chấp nhận bởi một ôtômát hữu hạn thì cũng được ký hiệu bởi một số biểu thức chính quy. ĐỊNH LÝ 3.4 : Nếu L được chấp nhận bởi một DFA, thì L được ký hiệu bởi một biểu thức chính quy. Chứng minh Đặt L là tập hợp được chấp nhận bởi DFA M ({q1, q2, , qn}, [U+F053], [U+F064], q1, F). Đặt Rkij là tập hợp tất cả các chuỗi x sao cho [U+F064](qi, x) = qj và nếu [U+F064](qi, y) = ql, với y là tiền tố bất kỳ của x, khác x hoặc [U+F065], thì l [U+F0A3] k. Tức là Rkij là tập hợp tất cả các chuỗi làm cho ôtômát đi từ trạng thái qi tới qj không đi ngang qua trạng thái nào (được đánh số) lớn hơn k. (Chú ý, khái niệm "đi ngang qua một trạng thái" có nghĩa là có phép chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k). Vì chỉ có n trạng thái nên Rnij sẽ là tập hợp tất cả các chuỗi làm ôtômát đi từ qi tới qj. Ta định nghĩa Rkij một cách đệ quy như sau: Rkij = Rk-1ik (Rk-1kk )* Rk-1kj È Rk-1ij (1) { a [U+F07C] [U+F064](qi, a) = qj } nếu i [U+F0B9] j R0ij = { a [U+F07C] [U+F064](qi, a) = qj } [U+F0C8] {[U+F065]} nếu i = j Một cách hình thức, Rkij định nghĩa như trên là các chuỗi nhập hay nguyên nhân đưa M từ qi tới qj không đi ngang qua trạng thái cao hơn qk, nghĩa là xảy ra hoặc một trong hai trường hợp sau : 1. Nằm trong Rk-1ij (để không bao giờ đi ngang qua một trạng thái nào cao như qk). 2. Bao gồm một chuỗi trong Rk-1ik (chuỗi làm M chuyển đến qk), theo sau bởi không hoặc nhiều chuỗi trong Rk-1kk (chuỗi làm M chuyển từ qk trở về qk mà không ngang qua qk hoặc một trạng thái nào cao hơn) và cuối cùng là một chuỗi trong Rk-1kj (chuỗi làm M chuyển từ qk đến qj ). Ta sẽ chỉ ra rằng với mỗi i, j và k tồn tại biểu thức chính quy rkij ký hiệu cho ngôn ngữ Rkij. Ta quy nạp theo k như sau: . k = 0 : khi đó R0ij là tập hợp hữu hạn các chuỗi có một ký hiệu hoặc [U+F065]. Vậy r0ij có thể viết dưới dạng a1 + a2 + + ap (hoặc a1 + a2 + + ap+ [U+F065] nếu i = j). Trong đó {a1, a2, , ap} là tập hợp tất cả các ký hiệu a sao cho [U+F064](qi, a) = qj. Nếu không có ký hiệu a nào như thế thì [U+F0C6] (hoặc [U+F065] khi i = j) ký hiệu cho r0ij. . Công thức (1) cho Rkij chỉ liên quan đến các phép toán trên biểu thức chính quy: hợp, nối kết, và bao đóng. Hơn nữa theo giả thiết quy nạp, với mỗi l, k và m tồn tại biểu thức chính quy rk-1lm sao cho L(rk-1lm) = Rk-1lm. Vậy đối với rkij ta có thể chọn biểu thức chính quy : (rk-1ik) (rk-1kk)* (rk-1kj) + rk-1ij Cuối cùng ta có nhận xét rằng L(M) = Èqj [U+F0CE] F Rn1j vì Rn1j ký hiệu cho tất cả các nhãn của tất cả các đường đi từ q1 tới qj.
34 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Vậy L(M) được ký hiệu bởi biểu thức chính quy r = rn1j1 + rn1j2+ + rn1jp, trong đó tập F = {qj1, qj2, , qjp} Thí dụ 3.15 : Viết biểu thức chính quy ký hiệu cho ngôn ngữ được chấp nhận bởi DFA sau : Figure 3.18 Hình 3.10 – DFA cho ví dụ 3.13 Gọi DFA được chỉ ra trong hình 3.10 là M ({q1, q2, q3}, {0, 1}, [U+F064], q1, {q2, q3}). Ta thấy, tập hợp tất cả các chuỗi được chấp nhận bởi DFA trên là các chuỗi làm cho ôtômát chuyển từ trạng thái bắt đầu q1 đến một trong hai trạng thái kết thúc q2 và q3 và không chuyển qua số tối đa là 3 (k = 3) trạng thái của ôtômát. Vậy ta cần viết biểu thức chính quy ký hiệu cho tập hợp này như sau : r = r312 + r313 Theo công thức đã được chứng minh trong Định lý, ta có thể tính được các giá trị rkij với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, như chỉ ra trong bảng sau: k = 0 k = 1 k = 2 rk11 [U+F065] [U+F065] (00)* rk12 0 0 0(00)* rk13 1 1 0*1 rk21 0 0 0(00)* rk22 [U+F065] [U+F065] + 00 (00)* rk23 1 1 + 01 0*1 rk31 [U+F0C6] [U+F0C6] (0 + 1)(00)*0 rk32 0 + 1 0 + 1 (0 + 1)(00)* rk33 [U+F065] [U+F065] [U+F065] + (0 + 1)0*1 Table 3.6 Bằng cách dùng các công thức tương đương như (r + s) t = rt + st và ([U+F065] + r)* = r* để đơn giản các biểu thức, chẳng hạn khi tính biểu thức : r122 = r021 (r011 )* r012 + r022 = 0([U+F065])*0 + [U+F065] = 00 + [U+F065] Tương tự, khi đơn giản biểu thức r213 = r112 (r122 )* r123 + r113 = 0(00 + [U+F065])*(1 + 01) + 1 ta nhận thấy (00 + [U+F065])* tương đương với (00)* và (1 + 01) thì tương đương với ([U+F065] + 0)1 nên ta rút gọn :
35 r213 = 0(00)*([U+F065] + 0)1 + 1 Mặt khác, chú ý rằng (00)*([U+F065] + 0) thì tương đương với 0*, vì thế 0(00)*([U+F065] + 0)1 + 1 cũng bằng 00*1 + 1 hay cuối cùng là 0*1. Để hoàn thành việc xây dựng biểu thức chính quy cho M, ta cần tính r312 và r313. Ta viết: r312 = r213 (r233 )* r232 + r212 = 0*1([U+F065] + (0 + 1)0*1)*(0 + 1)(00)* + 0(00)* = 0*1((0 + 1)0*1)*(0 + 1)(00)* + 0(00)* và r313 = r213 (r233 )* r233 + r213 = 0*1([U+F065] + (0 + 1)0*1)*([U+F065] + (0 + 1))0*1) + 0*1 = 0*1((0 + 1)0*1)* Vậy biểu thức chính quy có dạng : r = r312 + r313 = 0*1((0 + 1)0*1)*([U+F065] + (0 + 1)(00)*) + 0(00)* 3.4 MỘT VÀI ỨNG DỤNG CỦA ÔTÔMÁT HỮU HẠN Có nhiều kiểu phần mềm thiết kế nhằm đặc tả sự chuyển đổi tự động từ dạng biểu thức chính quy sang việc cài đặt máy tính một cách hiệu quả tương ứng với ôtômát hữu hạn. Trong phần này, ta sẽ đề cập đến hai ứng dụng trong số chúng. 3.4.1 Bộ phân tích từ vựng Các ký hiệu từ vựng (token) trong một ngôn ngữ lập trình thì hầu hết không có sự ngọai lệ, được biểu diễn như các tập hợp chính quy. Chẳng hạn, các định danh của ALGOL: các chữ cái viết hoa hoặc thường, theo sau bởi một dãy bất kỳ của chữ cái (letter) hoặc chữ số (digit) với độ dài không giới hạn có thể được biểu diễn như sau : (letter) (letter + digit)* trong đó "letter" thay thế cho A + B + + Z + a + b + + z và "digit" là 0 + 1 + + 9. Một ví dụ khác, các định danh của FORTRAN có độ dài giới hạn là 6 và các chữ cái chỉ cho phép dùng chữ viết hoa hoặc ký hiệu $ được biểu diễn như sau : (letter) ([U+F065] + letter + digit)5 với "letter" là $ + A + B + + Z . Trong SNOBOL, các hằng số số học có thể được biểu diễn như sau : ([U+F065] + [U+F02D]) (digit + ([U+F0B7] digit * + [U+F065]) + [U+F0B7] digit+ ) Một số công cụ phát sinh bộ phân tích từ vựng nhận input như một dãy các biểu thức chính quy mô tả các ký hiệu từ vựng và phát sinh một ôtômát hữu hạn đơn giản nhận dạng mọi ký hiệu từ vựng. Thông thường, chúng chuyển đổi biểu thức chính quy thành một NFA với [U+F065]-dịch chuyển và sau đó xây dựng tập hợp con các trạng thái để có thể phát sinh DFA một cách trực tiếp hơn là tìm cách loại bỏ các phép chuyển nhãn [U+F065]. Mỗi trạng thái kết thúc xác định ký hiệu từ vựng cụ thể đã tìm thấy. Hàm chuyển của FA sẽ được mã hóa bằng một trong vài cách nhằm chiếm ít không gian hơn so với bảng hàm chuyển tổ chức dưới dạng mảng hai chiều. Bộ phân tích từ vựng được thiết lập bằng cách phát sinh một chương trình cố định thông dịch các bảng mã, cùng với các bảng minh họa cụ thể sự nhận dạng của FA trên các ký hiệu từ vựng (viết dưới dạng các biểu thức chính quy). Bộ phân tích từ vựng dạng này có thể được dùng như một chương trình con độc lập (module) trong một trình biên dịch ngôn ngữ. 3.4.2 Trình soạn thảo văn bản Hiển nhiên, các trình soạn thảo văn bản hoặc các chương trình tương tự cho phép thay thế một chuỗi bởi mọi chuỗi kết hợp với một biểu thức chính quy cho trước. Chẳng hạn, trình soạn thảo văn bản ed trong UNIX cho phép một câu lệnh như sau : /aba*c/
36 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY để tìm sự xuất hiện đầu tiên của chuỗi có dạng như trên. Hay câu lệnh : s/bbb*/b/ cho phép thay thế các chuỗi có dạng bbb* thành chuỗi có một ký tự b. Hay trong các câu lệnh của MS-DOS và NC, ví dụ câu lệnh : Del tmp*.??? sẽ cho phép xóa đi tất cả các file với tên tập tin bắt đầu bằng tmp, sau đó là một chuỗi bắt kỳ và có phần mở rộng là 3 ký tự tùy ý. Dấu * trong trường hợp này ký hiệu cho một chuỗi bất kỳ, còn dấu ? ký hiệu cho một ký tự tùy ý. Đây cũng là một dạng ký hiệu của biểu thức chính quy thay thế cho chuỗi. Hay chẳng hạn, một ví dụ về xử lý chuỗi khác được áp dụng cho việc tìm kiếm theo mẫu trên các trang Web. Trong tất cả các ví dụ trên, ký hiệu * xác định “mọi” biểu thức a1 + a2 + + an trong đó các ai là tất cả các ký tự cho phép trong máy tính trừ ký tự xuống dòng (newline). Ta có thể chuyển một biểu thức chính quy r sang DFA chấp nhận mọi r. Chú ý rằng sự hiện diện của ký hiệu * sẽ cho phép ta nhận dạng một thành phần của L(r) bắt đầu từ bất kỳ vị trí nào trong dòng. Để làm được điều này, các ứng dụng phải thực hiện quá trình chuyển đổi từ một biểu thức chính quy sang NFA. Và vì cơ chế hoạt động của NFA khá phức tạp nên thông thường ngay sau đó, NFA lại phải được biến đổi tiếp thành dạng DFA tương đương. Tuy nhiên, sự chuyển đổi từ một biểu thức chính quy sang DFA tốn nhiều thời gian hơn việc sử dụng DFA để kiểm tra các mẫu bằng cách duyệt qua chúng một lần, tuy DFA có thể có số trạng thái là hàm mũ của độ dài biểu thức chính quy. Thực tế, trong trình soạn thảo văn bản UNIX, biểu thức chính quy với mọi r được chuyển thành một NFA có [U+F065]-dịch chuyển và sau đó NFA này được mô phỏng một cách trực tiếp. Câu hỏi : ? Hãy tự liên hệ một số các ứng dụng thực tế khác dùng cơ chế ôtômát hữu hạn ? Tổng kết chương III: Phần nội dung chương III tập trung nghiên cứu cơ chế hoạt động của các dạng ôtômát hữu hạn, mối tương quan giữa chúng, cũng như sự tương đương của chúng với biểu thức chính quy. Tùy theo các yêu cầu thực tế của ứng dụng, ta có thể chuyển từ dạng phức tạp nhất sang các dạng đơn giản hơn. Có thể tóm tắt sự tương quan giữa các Định lý trong chương này theo sơ đồ sau : Figure 3.19 BÀI TẬP CHƯƠNG III 3.1. Mô tả ngôn ngữ được chấp nhận bởi các ôtômát hữu hạn với sơ đồ chuyển được cho như sau : a)
37 Figure 3.20 b) Figure 3.21 3.2. Xây dựng các sơ đồ chuyển ôtômát hữu hạn chấp nhận các ngôn ngữ sau trên bộ chữ cái [U+F053] = {0, 1} 1. Tập các chuỗi kết thúc là 00. 2. Tập các chuỗi có 3 ký hiệu 0 liên tiếp. c) Tập các chuỗi mà ký hiệu thứ 3 kể từ cận phải của chuỗi là 1. d) Tập mọi chuỗi mà bất cứ chuỗi con nào có độ dài bằng 5 đều có chứa ít nhất 2 con số 0. 3.3. Tìm các sơ đồ chuyển ôtômát hữu hạn đoán nhận các ngôn ngữ sau : a) Tập các chuỗi trên {0, 1} có chứa một số chẵn các số 0 và một số lẻ các số 1 b) Tập các chuỗi trên {0, 1} có độ dài chia hết cho 3. c) Tập các chuỗi trên {0, 1} không chứa 101 như một chuỗi con. 3.4. Xây dựng DFA tương đương với mỗi NFA sau : a) N1({0,1,2,3},{a,b},[U+F064]1,0,{3}) với [U+F064]1 b) N2 ({0,1,2,3}, {a,b}, [U+F064]2,0, {1,3}) với [U+F064]2 [U+F064]1 a b[U+F064]2 a b 0 {0, 1}{1}0 {1, 3}{1} 1 {2}{2}1 {2}{1, 2} 2 {3}[U+F0C6]2 {3}{0} 3 {3}{3}3 [U+F0C6]{0} c)
38 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Figure 3.22 d) Figure 3.23 3.5. Tìm NFA không có [U+F065]-dịch chuyển nhận dạng cùng ngôn ngữ với các NFA sau : a) Figure 3.24 b)
39 Figure 3.25 3.6. Viết biểu thức chính quy và vẽ NFA đoán nhận các ngôn ngữ sau : 1. Tập hợp các chuỗi trên [U+F053] = {1, 2, 3} sao cho ký hiệu cuối cùng đã có xuất hiện trước đó . 2. Tập hợp các chuỗi trên [U+F053] = {0, 1} trong đó có một cặp ký tự 0 cách nhau bởi một chuỗi con có độ dài 4i, với i [U+F0B3] 0 nào đó. 3.7. Viết biểu thức chính quy cho mỗi ngôn ngữ sau trên [U+F053] = { 0, 1} : a) Tập hợp các chuỗi trong đó mọi cặp 0 liên tiếp đều xuất hiện trước mọi cặp 1 liên tiếp. b) Tập hợp các chuỗi chứa nhiều nhất một cặp 0 liên tiếp và nhiều nhất một cặp 1 liên tiếp. 3.8. Mô tả (bằng lời) ngôn ngữ được các biểu thức chính quy sau đặc tả : 1. 0(0 + 1)* 0 2. (0+ 1)*0(0 + 1) (0 + 1) 3. (11+ 0)*(00+ 1) 4. (1+ 01+ 001)*([U+F065] + 0 + 00) 00 + 11 + (01+ 10) (00+ 11)*(01+ 10) * 3.9. Chứng tỏ các biểu thức chính quy sau ký hiệu cho cùng một ngôn ngữ : (aa)*,(aa)* + ([U+F0C6]a),(aa + aaaa)*,(aa)* (aa)* 3.10. Vẽ NFA với [U+F065]-dịch chuyển được cho bởi các biểu thức chính qui sau. Sau đó, hãy chuyển sang DFA tương đương : 1. ( a* + b*)* 2. (([U+F065] + a) b*)* 3. (a + b)* abb (a + b)* 4. ab + (a + bb) a*b 5. (a + ab + aab)*([U+F065]+ a+ aa) 6. 10 + (0 + 11)0*1 7. 01 [ (( 10)*+ 111)* + 0]*1 3.11. Hãy tìm các biểu thức chính qui tương ứng với các sơ đồ chuyển trạng thái sau: a)b)
40 CHƯƠNG 3. ÔTÔMAT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Figure 3.26 Figure 3.27 BÀI TẬP LẬP TRÌNH 3.12. Viết chương trình trong Pascal / C mô phỏng một FA chấp nhận ngôn ngữ được biểu diễn bởi biểu thức chính quy sau : [ A Z, a Z ]+ [ A Z, a Z, 0 9, _ ]* + [ 0 9]+ + op 3.13. Viết chương trình cho ra một FA tương ứng khi đầu vào là một biểu thức chính quy. 3.14. Viết chương trình cho ra DFA khi đầu vào là một NFA.
Chương 4 Văn phạm phi ngữ cảnh1 4.1 VĂN PHẠM PHI NGỮ CẢNH (CFG : Context Free Grammar) 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 các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ như sau : [U+F0AE] [U+F0AE] [U+F0AE] [U+F0AE] [U+F0AE] An [U+F0AE] sinh viên [U+F0AE] là [U+F0AE] 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 luật sinh trong văn phạm phi ngữ cảnh. Và như vậy, văn phạm phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự nhiên. Tuy nhiên, trong khoa học máy tính, với nhu cầu biểu diễn các ngôn ngữ lập trình, văn phạm phi ngữ cảnh CFG còn được thiết kế thành một dạng tương đương gọi là văn phạm BNF (Backus - Naur Form). Đây cũng là văn phạm CFG với những thay đổi nhỏ về dạng thức và một số ký hiệu viết tắt mà các nhà khoa học máy tính thường ứng dụng trong việc diễn tả cú pháp của các ngôn ngữ lập trình cấp cao (như ALGOL, PASCAL, ). Trong dạng thức của văn phạm BNF, ký hiệu ::= được dùng thay cho ký hiệu [U+F0AE]. Chẳng hạn, để định nghĩa một biểu thức số học (expression) bao gồm các danh biểu (identifier) tham gia vào các phép toán +, * hoặc biểu thức con lồng trong dấu ngoặc đơn , ta viết : ::= + ::= * ::= ( ) ::= Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân tích cú pháp vận dụng trong chương trình dịch và cho nhiều ứng dụng khác về xử lý chuỗi. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình mà biểu thức chính quy không thể đặc tả. 1This content is available online at . 41
42 CHƯƠNG 4. VĂN PHẠM PHI NGỮ CẢNH 4.1.1 Định nghĩa Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ được biểu diễn bởi các biến được mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là ký hiệu kết thúc. Quy tắc quan hệ giữa các biến gọi là luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một chuỗi có thể gồm biến lẫn các ký hiệu kết thúc trong văn phạm. Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu là văn phạm G (V, T, P, S), trong đó : . V là tập hữu hạn các biến (hay ký tự chưa kết thúc) . T là tập hữu hạn các ký tự kết thúc, V [U+F0C7] T = [U+F0C6] . P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A [U+F0AE] [U+F061] với A là biến và [U+F061] là chuỗi các ký hiệu [U+F0CE] (V [U+F0C8] T)* . S là một biến đặc biệt gọi là ký hiệu bắt đầu văn phạm. Thí dụ 5.1 : Văn phạm G ({S, A, B}, {a, b}, P, S ), trong đó P gồm các luật sinh sau: S ® AB A ® aA A ® a B ® bB B ® b Quy ước ký hiệu: - Các chữ in hoa A, B, C, D, E, và S ký hiệu các biến (S thường được dùng làm ký hiệu bắt đầu ). - Các chữ nhỏ a, b, c, d, e, ; các chữ số và một số ký hiệu khác ký hiệu cho các ký hiệu kết thúc. - Các chữ in hoa X, Y, Z là các ký hiệu có thể là ký hiệu kết thúc hoặc biến. - Các chữ Hi-lạp [U+F061], [U+F062], [U+F067], biểu diễn cho chuỗi các ký hiệu kết thúc và biến. Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh của nó. Nếu A ® [U+F061]1, A ® [U+F061]2 , , A ® [U+F061]k là các luật sinh của biến A trong văn phạm nào đó, ta sẽ ghi ngắn gọn là A ® [U+F061]1 | [U+F061]2 | | [U+F061]k Thí dụ 5.2 : Văn phạm trong Thí dụ 5.1 trên có thể viết gọn là : S ® AB A ® aA [U+F07C] a B ® bB [U+F07C] b Câu hỏi : ? Bạn nghĩ gì về lớp ngôn ngữ có thể được sinh bởi văn phạm trong ví dụ trên ? Cơ chế nào có thể được sử dụng cho văn phạm để phát sinh ngôn ngữ ? 4.1.2 Dẫn xuất và ngôn ngữ Dẫn xuất: Để định nghĩa ngôn ngữ sinh bởi văn phạm CFG G (V, T, P, S), ta dẫn nhập khái niệm dẫn xuất. Trước hết ta giới thiệu hai quan hệ [U+F0DE]G và [U+F0DE]*G giữa hai chuỗi trong tập (V [U+F0C8] T)*. Nếu A [U+F0AE] [U+F062] là một luật sinh trong văn phạm và [U+F061], [U+F067] là hai chuỗi bất kỳ trong tập (V [U+F0C8] T)* thì [U+F061]A[U+F067] [U+F0DE]G [U+F061][U+F062][U+F067], hay ta còn nói luật sinh A [U+F0AE] [U+F062] áp dụng vào chuỗi [U+F061]A[U+F067] để thu được chuỗi [U+F061][U+F062][U+F067], nghĩa là [U+F061]A[U+F067] sinh trực tiếp [U+F061][U+F062][U+F067] trong văn phạm G. Hai chuỗi gọi là quan hệ nhau bởi [U+F0DE]G nếu chuỗi thứ hai thu được từ chuỗi thứ nhất bằng cách áp dụng một luật sinh nào đó. Giả sử [U+F061]1, [U+F061]2, , [U+F061]m là các chuỗi thuộc (V [U+F0C8] T)* với m [U+F0B3] 1 và : [U+F061]1 [U+F0DE]G [U+F061]2, [U+F061]2 [U+F0DE]G [U+F061]3, , [U+F061]m -1 [U+F0DE]G [U+F061]m thì ta nói [U+F061]1[U+F0DE]*G [U+F061]m hay [U+F061]1 dẫn xuất ra [U+F061]m trong văn phạm G.
43 Như vậy, [U+F0DE]*G là bao đóng phản xạ và bắc cầu của [U+F0DE]G. Nói cách khác, [U+F061] [U+F0DE]*G [U+F062] nếu [U+F062] được dẫn ra từ [U+F061] bằng không hoặc nhiều hơn các luật sinh của P. Chú ý rằng [U+F061] [U+F0DE]*G [U+F061] với mọi chuỗi [U+F061]. Thông thường nếu không có nhầm lẫn ta sẽ dùng các ký hiệu [U+F0DE] và [U+F0DE]* thay cho ký hiệu [U+F0DE]G và [U+F0DE]*G. Nếu [U+F061] dẫn ra [U+F062] bằng i bước dẫn xuất thì ta ký hiệu [U+F061] [U+F0DE]i [U+F062]. Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh Cho văn phạm CFG G(V, T, P, S), ta định nghĩa : L(G) = {w[U+F0BD]w [U+F0CE] T * và S [U+F0DE]*G w} Nghĩa là, một chuỗi thuộc L(G) nếu: 1) Chuỗi gồm toàn ký hiệu kết thúc. 2) Chuỗi được dẫn ra từ ký hiệu bắt đầu S. Ta gọi L là ngôn ngữ phi ngữ cảnh (CFL) nếu nó là L(G) với một CFG G nào đó. Chuỗi [U+F061] gồm các ký hiệu kết thúc và các biến, được gọi là một dạng câu sinh từ G nếu S [U+F0DE]*[U+F061]. Hai văn phạm G1, G2 được gọi là tương đương nếu L(G1) = L(G2) Thí dụ 5.3 : Xét văn phạm G (V, T, P, S), trong đó : V = {S}, T = {a, b}, P = {S ® aSb, S ® ab}. Bằng cách áp dụng luật sinh thứ nhất n -1 lần và luật sinh thứ hai 1 lần, ta có: S aSb aaSbb a3Sb3 an-1bn-1 anbn Vậy, L(G) chứa các chuỗi có dạng anbn, hay L(G) = {anbn [U+F07C] n [U+F0B3] 1}. 4.1.3 Cây dẫn xuất Để dễ hình dung sự phát sinh ra các chuỗi trong văn phạm phi ngữ cảnh, ta thường diễn tả một chuỗi dẫn xuất qua hình ảnh một cây. Một cách hình thức, ta định nghĩa như sau: Định nghĩa : Cho văn phạm G (V, T, P, S). Cây dẫn xuất (hay cây phân tích cú pháp) của G được định nghĩa như sau : i) Mỗi nút (đỉnh) có một nhãn, là một ký hiệu [U+F0CE] (V [U+F0C8] T [U+F0C8] {[U+F065]}) ii) Nút gốc có nhãn là ký hiệu bắt đầu S. iii) Nếu nút trung gian có nhãn A thì A [U+F0CE] V iv) Nếu nút n có nhãn A và các đỉnh n1, n2, , nk là con của n theo thứ tự từ trái sang phải có nhãn lần lượt là X1, X2, , Xk thì A [U+F0AE] X1X2 Xk là một luật sinh trong tập luật sinh P. v) Nếu nút n có nhãn là từ rỗng [U+F065] thì n phải là nút lá và là nút con duy nhất của nút cha của nó. Thí dụ 5.4 : Xét văn phạm G ({S, A}, {a, b}, P, S), trong đó P gồm: S ® aAS | a A ® SbA | SS | ba Một cây dẫn xuất từ văn phạm có dạng như hình 5.1 sau : Ta thấy, nút 1 có nhãn S và các con của nó lần lượt là a, A, S (chú ý S [U+F0AE] aAS là một luật sinh). Tương tự, nút 3 có nhãn A và các con của nó là S, b, A (từ luật sinh A [U+F0AE] SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a (luật sinh S [U+F0AE] a). Cuối cùng nút 7 có nhãn A và có các nút con b, a (luật sinh A [U+F0AE] ba). Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có một dạng câu trong G. Ta gọi chuỗi này là chuỗi sinh bởi cây dẫn xuất.
44 CHƯƠNG 4. VĂN PHẠM PHI NGỮ CẢNH Figure 4.1 Hình 5.1 - Cây dẫn xuất từ văn phạm Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn được gọi là A-cây con (hoặc A-cây). Cây con cũng giống như cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký hiệu bắt đầu S. Thí dụ 5.5 :Xét văn phạm và cây dẫn xuất trong Hình 5.1. Đọc các lá theo thứ tự từ trái sang phải ta có chuỗi aabbaa, trong trường hợp này tất cả các lá đều là ký hiệu kết thúc, nhưng nói chung cũng không bắt buộc như thế, lá có thể có nhãn là [U+F065] hoặc biến. Ta thấy dẫn xuất S [U+F0DE]* aabbaa bằng chuỗi dẫn xuất : S aAS aSbAS aabAS aabbaS aabbaa A-cây có nút đỉnh là 3 tạo ra chuỗi con abba theo chuỗi dẫn xuất : S SbA abA abba Câu hỏi : ? Các cây dẫn xuất được sinh từ những chuỗi dẫn xuất khác nhau cho cùng một chuỗi nhập có là những cây dẫn xuất khác nhau không ? 4.1.4 Quan hệ giữa dẫn xuất và cây dẫn xuất ĐỊNH LÝ 5.1 : Nếu G (V, T, P, S) là một văn phạm phi ngữ cảnh thì S [U+F0DE]* [U+F061] nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra [U+F061]. 4.2 Chứng minh Ta chứng minh rằng với biến A bất kỳ, A [U+F0DE]*[U+F061] nếu và chỉ nếu có một A-cây sinh ra [U+F061]. Nếu: Giả sử [U+F061] được sinh bởi A-cây, ta chứng minh quy nạp theo số nút trung gian của cây dẫn xuất rằng A [U+F0DE]*[U+F061].
45 Nếu có 1 nút trung gian thì cây phải có dạng như hình sau : Khi đó X1X2 Xn là chuỗi [U+F061] và A [U+F0AE] [U+F061] là một luật sinh trong P theo định nghĩa cây dẫn xuất. Figure 4.2 Hình 5.2(a) - A-cây với một nút trong Giả sử kết quả đúng tới k -1 nút trung gian ( k > 1) Ta chứng minh kết quả cũng đúng với k nút. Xét [U+F061] được sinh ra bởi A-cây có k nút trung gian. Rõ ràng các nút con của nút gốc không phải tất cả đều là lá, ta gọi chúng từ trái sang phải là X1, X2, , Xn thì chắc chắn rằng A [U+F0AE] X1X2 Xn là một luật sinh. Xét nút Xi bất kỳ : - Nếu Xi không là nút lá thì Xi phải là một biến và Xi - cây con sẽ sinh ra một chuỗi [U+F061]i nào đó. - Nếu Xi là nút lá, ta đặt [U+F061]i = Xi. Dễ thấy rằng nếu j < i thì các [U+F061]j ở bên trái [U+F061]j, do vậy chuỗi đọc từ lá vẫn có dạng [U+F061] = [U+F061]1[U+F061]2 [U+F061]n. Mỗi Xi - cây con phải có ít nút trung gian hơn cây ban đầu, vì thế theo giả thiết quy nạp, với mỗi đỉnh i không phải là lá thì Xi [U+F0DE]*[U+F061]i. Vậy A [U+F0DE] X1X2 Xn [U+F0DE]* [U+F061]1X2 Xn [U+F0DE]* [U+F061]1[U+F061]2X3 Xn [U+F0DE]* [U+F0DE]* [U+F061]1[U+F061]2 [U+F061]n = [U+F061] Hay ta có A [U+F0DE]* [U+F061] . Chú ý rằng đây chỉ là một trong nhiều cách dẫn xuất ra [U+F061]. Chỉ nếu : Ngược lại, giả sử A [U+F0DE]* [U+F061] ta cần chỉ ra một A - cây sinh ra [U+F061]. Nếu A [U+F0DE]* [U+F061] bằng một bước dẫn xuất thì A [U+F0AE] [U+F061] là một luật sinh trong P và có cây dẫn xuất sinh ra [U+F061] như trong hình trên. Giả sử kết quả đúng tới k-1 bước dẫn xuất Xét A [U+F0DE]* [U+F061] bằng k bước dẫn xuất, gọi bước đầu tiên là A [U+F0AE] X1X2 Xn. Rõ ràng, một ký hiệu trong [U+F061] phải được dẫn ra từ một biến Xi nào đó. Vì vậy, ta có thể viết [U+F061] = [U+F061]1[U+F061]2 [U+F061]n, trong đó mỗi 1 [U+F0A3] i [U+F0A3] n thoả mãn : - [U+F061]i = Xi nếu Xi là ký hiệu kết thúc. - Xi [U+F0DE]* [U+F061]i nếu Xi là một biến. Nếu Xi là biến thì dẫn xuất của [U+F061]i từ Xi phải có ít hơn k bước. Vì vậy, theo giả thiết quy nạp ta có Xi - cây sinh ra [U+F061]i, đặt cây này là Ti Bây giờ ta dựng A - cây có n lá X1X2 Xn. Mỗi Xi không là ký hiệu kết thúc ta thay bằng cây Ti tương ứng. Cuối cùng, ta có cây dẫn xuất sinh ra có dạng như sau :
46 CHƯƠNG 4. VĂN PHẠM PHI NGỮ CẢNH Figure 4.3 Hình 5.2(b) - A-cây Thí dụ 5.6 :Xét chuỗi dẫn xuất S [U+F0DE]* aabbaa cho văn phạm ở Thí dụ 5.4. Bước đầu tiên trong dẫn xuất đó là S [U+F0AE] aAS. Theo dõi các bước suy dẫn sau đó, ta thấy biến A được thay bởi SbA, rồi trở thành abA và cuối cùng thành abba, đó chính là kết quả của cây T2 (A - cây). Còn biến S thì được thay bởi a và đó là kết quả của cây T3 (S -cây). Ghép nối lại, ta được cây dẫn xuất mà kết quả là chuỗi aabbaa như dưới đây. Figure 4.4 [ Hình 5.3 - Ghép nối các cây dẫn xuất
47 4.2.1 Dẫn xuất trái nhất, dẫn xuất phải nhất Nếu tại mỗi bước dẫn xuất, luật sinh được áp dụng vào biến bên trái nhất thì ta gọi đó là dẫn xuất trái nhất (leftmost) hay dẫn xuất trái. Tương tự, nếu biến bên phải nhất được thay thế ở mỗi bước dẫn xuất, đó là dẫn xuất phải nhất (rightmost) hay dẫn xuất phải. Nếu chuỗi w [U+F0CE] L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và tương ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó có thể có nhiều cây dẫn xuất. Thí dụ 5.7 : Xét cây dẫn xuất ở Hình 5.1 . Dẫn xuất trái nhất của cây : S aAS aSbAS aabAS aabbaS aabbaa. . Dẫn xuất phải nhất tương ứng là : S aAS aAa aSbAa aSbbaa aabbaa. 4.2.2 Văn phạm mơ hồ Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w, thì G được gọi là văn phạm mơ hồ (ambiguity). Dĩ nhiên, cũng có thể nói rằng văn phạm G là mơ hồ nếu có một chuỗi w được dẫn ra từ ký hiệu bắt đầu S với hai dẫn xuất trái hoặc hai dẫn xuất phải. Thí dụ 5.8 : Xét văn phạm G với các luật sinh như sau : E [U+F0AE] E + E [U+F07C] E*E [U+F07C] (E) [U+F07C] a Văn phạm này sinh ra các chuỗi biểu thức số học với 2 phép toán + và * . Với chuỗi a + a * a, ta có thể vẽ đến hai cây dẫn xuất khác nhau như sau : Figure 4.5 (a) (b) Hình 5.4 - Các cây dẫn xuất khác nhau cho cùng chuỗi nhập Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo hai cách khác nhau: thực hiện phép cộng trước hay phép nhân trước ? Để khắc phục sự mơ hồ này, ta có thể : - Hoặc quy định rằng các phép cộng và nhân luôn luôn được thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G1 không mơ hồ tương đương như sau : E [U+F0AE] E + T [U+F07C] E*T [U+F07C] T
48 CHƯƠNG 4. VĂN PHẠM PHI NGỮ CẢNH T [U+F0AE] (E) [U+F07C] a - Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn luôn được ưu tiên hơn phép cộng. Ta viết văn phạm G2 không mơ hồ tương đương như sau : E [U+F0AE] E + T [U+F07C] T T [U+F0AE] T*F [U+F07C] F F [U+F0AE] (E) [U+F07C] a 4.3 GIẢN LƯỢC CÁC VĂN PHẠM PHI NGỮ CẢNH Thường thì một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài yếu tố thừa, vô ích. Chẳng hạn như theo các đặc tính trên, có những ký hiệu không thực sự tham gia vào quá trình dẫn xuất ra câu, hoặc sẽ có những luật sinh dạng A [U+F0AE] B làm kéo dài chuỗi dẫn xuất một cách không cần thiết. Vì vậy, việc giản lược văn phạm phi ngữ cảnh là nhằm loại bỏ những yếu tố vô ích đó mà không làm giảm bớt khả năng sản sinh ngôn ngữ của văn phạm. Nếu L là một CFL, nó có thể tạo ra văn phạm CFG với các đặc tính sau : 1. Mỗi biến và mỗi ký hiệu kết thúc của G đều xuất hiện trong dẫn xuất của một số chuỗi trong L. 2. Không có luật sinh nào dạng A [U+F0AE] B, mà trong đó A, B đều là biến. Hơn nữa, nếu [U+F065] [U+F0CF] L thì không cần luật sinh A [U+F0AE] [U+F065]. Thực tế, nếu [U+F065] [U+F0CF] L, ta có mọi luật sinh trong G đều có một trong hai dạng : A [U+F0AE] BC hoặc A [U+F0AE] a[U+F061] ([U+F061] là chuỗi các biến hoặc [U+F065]) A [U+F0AE] a Hai dạng đặc biệt này gọi là dạng chuẩn Chomsky và dạng chuẩn Greibach. 4.3.1 Các ký hiệu vô ích Một ký hiệu X gọi là có ích nếu có một dẫn xuất S [U+F0DE]* [U+F061]X[U+F062] [U+F0DE]* w với các chuỗi [U+F061], [U+F062] bất kỳ và w [U+F0CE] T *. Ngược lại X gọi là vô ích. Vậy, có 2 đặc điểm cho ký hiệu có ích: - X phải dẫn ra một chuỗi ký hiệu kết thúc. - X phải nằm trong dẫn xuất từ S. Tuy nhiên 2 dấu hiệu trên không đủ để đảm bảo X có ích vì X có thể nằm trong dạng câu chứa một biến nhưng từ đó không có ký hiệu kết thúc được sinh ra. BỔ ĐỀ 1: (Dùng loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc) Cho CFG G (V, T, P, S) với L(G) [U+F0B9] [U+F0C6], có một CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi A [U+F0CE] V’ tồn tại w [U+F0CE] T* để A [U+F0DE]* w. Chứng minh Mỗi biến A với luật sinh A [U+F0AE] w trong P thì rõ ràng A [U+F0CE] V’. Nếu A [U+F0AE] X1X2 Xn là một luật sinh, trong đó mỗi Xi hoặc là ký hiệu kết thúc hoặc là một biến đã có sẵn trong V’ thì một chuỗi các ký hiệu kết thúc có thể được dẫn ra từ A bằng dẫn xuất bắt đầu A [U+F0DE] X1X2 Xn, vì vậy A [U+F0CE] V’. Tập V’ có thể tính được bằng cách lặp lại giải thuật trên. P’ là tập tất cả các luật sinh mà các ký hiệu của nó thuộc V’ [U+F0C8] T. Giải thuật tìm V’ như sau: Begin (1) OLDV:= Æ; (2) NEWV:= {A [U+F07C] A [U+F0AE] w với w [U+F0CE] T *}; (3) While OLDV 1 NEWV do begin (4) OLDV := NEWV;
49 (5) NEWV := OLDV [U+F0C8] {A [U+F07C] A [U+F0AE] [U+F061] với [U+F061] [U+F0CE] (T [U+F0C8] OLDV)*} end; (6) V’ := NEWV; end; Rõ ràng rằng nếu biến A được thêm vào V’ tại bước (2) hoặc (5) thì A sẽ dẫn ra được chuỗi ký hiệu kết thúc. Ta chứng minh rằng nếu A dẫn ra được một chuỗi ký hiệu kết thúc thì A được thêm vào tập NEWV. Dùng chứng minh quy nạp theo độ dài của dẫn xuất A [U+F0DE]* w. Nếu độ dài bằng 1 thì A [U+F0AE] [U+F061] là một luật sinh trong P. Vậy A được đưa vào V’ tại bước (2). Giả sử kết quả đúng tới k -1 bước dẫn xuất ( k >1) Nếu A [U+F0DE] X1X2 Xn [U+F0DE]* w bằng k bước thì ta có thể viết w = w1w2 wn, trong đó Xi [U+F0DE]* wi, với 1 [U+F0A3] i [U+F0A3] n bằng ít hơn k bước dẫn xuất. Theo giả thiết quy nạp thì các biến Xi này được thêm vào V’. Khi Xi cuối cùng được thêm vào V’ thì vòng lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ được thêm vào V’ tại (5). Ta chứng minh L(G’) = L(G) : Chọn V’ là tập hợp tại (6) và P’ là tập tất cả các luật sinh mà các ký hiệu của nó thuộc (V’ [U+F0C8] T) thì chắc chắn rằng có tồn tại văn phạm G’ (V’, T, P’, S) thoả mãn tính chất: nếu A [U+F0CE] V’ thì A [U+F0DE]* w với w nào đó thuộc T *. Hơn nữa, mỗi luật sinh của P’ đều là luật sinh của P nên ta có L(G’) [U+F0CD] L(G). Ngược lại giả sử một từ w [U+F0CE] L(G) - L(G’) thì một dẫn xuất bất kỳ của w phải liên quan đến các biến thuộc V – V’ hoặc luật sinh thuộc P – P’ (các dẫn xuất này đưa ra các biến thuộc V – V’), nhưng do không có biến nào trong V – V’ dẫn đến chuỗi kết thúc, điều này dẫn đến mâu thuẫn. Vậy L(G’) = L(G). Hay có thể nói 2 ngôn ngữ được cho từ 2 văn phạm G và G’ là tương đương nhau, hay nói cách khác: nếu có một văn phạm G thì luôn luôn có một văn phạm G’ tương ứng mà trong đó mỗi biến của G’ đều cho ra ký hiệu kết thúc. BỔ ĐỀ 2: (Dùng loại bỏ các biến không được dẫn ra từ ký hiệu bắt đầu văn phạm) Nếu G (V, T, P, S) là CFG thì ta có thể tìm được CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi X [U+F0CE] V’ [U+F0C8] T’ tồn tại [U+F061], [U+F062] [U+F0CE] (V’ [U+F0C8] T’)* để S [U+F0DE]* [U+F061]X[U+F062]. Chứng minh Tập V’ [U+F0C8] T’ gồm các ký hiệu xuất hiện trong dạng câu của G được xây dựng bởi giải thuật lặp như sau : . Đặt V’ = {S}; T’ = [U+F0C6]; . Nếu A [U+F0CE] V’ và A [U+F0AE] [U+F061]1| [U+F061]2 | | [U+F061]n là các luật sinh trong P thì thêm tất cả các biến của [U+F061]1, [U+F061]2, , [U+F061]n vào V’ và các ký hiệu kết thúc của [U+F061]1, [U+F061]2 , , [U+F061]n vào T’. . Lặp lại giải thuật cho đến khi không còn biến hoặc ký hiệu kết thúc nào được thêm vào nữa. Dễ thấy, X [U+F0CE] V’ [U+F0C8] T’ thì tồn tại [U+F061], [U+F062] [U+F0CE] (V’ [U+F0C8] T’)* để S [U+F0DE]* [U+F061]X[U+F062], trong đó P’ là tập hợp tất cả các luật sinh của P chỉ chứa các ký hiệu thuộc (V’ [U+F0C8] T’). Ta dễ dàng chứng minh L(G’) = L(G) . ĐỊNH LÝ 5.2: Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng được sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký hiệu vô ích. Chứng minh Đặt L = L(G) là CFL không rỗng. Đặt G1 là kết quả của việc áp dụng bổ đề 1 vào G và G2 là kết quả của việc áp dụng bổ đề 2 vào G1. Giả sử G2 có ký hiệu vô ích là X. Theo bổ đề 2 ta có S [U+F0DE]*G2 [U+F061]X[U+F062]. Vì tất cả các ký hiệu trong G2 đều có trong G1 nên theo bổ đề 1: S [U+F0DE]*G1 [U+F061]X[U+F062] [U+F0DE]*G1 w với