Lý thuyết tính toán

1Lý thuyết tính toán (Theory of Computation) PGS.TS. Phan Huy Khánh khanhph@vnn.vn Chương 1 Mở đầu 2/56 Chào mọi người ! Bonjour Tout le Monde ! Hello Everyone! 他 ﺾ 好 ! Привет Kаждый ! 3/56 Mục đích môn học Môn học Lý thuyết tính toán (Theory of Computation) cung cấp những kiến thức cơ bản về :  Các mô hình tính toán lý thuyết :  Các máy truy cập ngẫu nhiên  Các ôtômat hữu hạn trạng thái  Ngôn ngữ hình thức và văn phạm  Lý thuyết độ phức tạp tính toán  Máy Turing và khái niệm tính được  Các hàm đệ quy  Các khái niệm về bài toán, thuật toán, tính giải được, tính quyết định... 4/56 Kiến thức yêu cầu  Môn học yêu cầu một số kiến thức tiên quyết :  Tin học đại cương  Toán rời rạc  Cấu trúc dữ liệu và giải thuật  Sinh viên nắm được :  Các mô hình tính toán tổng quát  Các khái niệm cơ bản về độ phức tạp tính toán, phương pháp chứng minh hình thức  Có khả năng minh hoạ hoạt động của các mô hình đó bằng thuật toán, chương trình 5/56 Tài liệu tham khảo  Giáo trình PPT “Lý thuyết Tính toán”   www.cs.berkeley.edu/~vandam/CS172/  Keywords to findout on internet (Google):  Computation | Computing Theory  Computability | Decidability  Formal Language | Automata Theory  Set | Graph Theory 6/56 Đánh giá kết quả học tập  Yêu cầu :  Hiểu nội dung trình bày trên lớp  Thực hiện các bài tập về nhà  Khả năng thực hành  Tinh thần thái độ và năng lực học tập  Nghe giảng, ghi chép  Trả lời và đặt câu hỏi  Tham khảo tài liệu, truy cập internet  Tham gia học nhóm, tập thảo luận và thuyết trình   Kiểm tra cuối kỳ :  Thi viết (60 phút) 27/56 Nội dung môn học Chương 1 Mở đầu : cơ sở của môn học Chương 2 Ôtômat hữu hạn Chương 3 Văn phạm và ôtômat đẩy xuống Chương 4 Máy Turing Chương 5 Hàm đệ quy Chương 6 Máy RAM Chương 7 Lý thuyết độ phức tạp tính toán 8/56 Đâu là giới hạn của Tin học ?  Nghiên cứu về bài toán (problem) :  Lớp các bài toán giải được (resolvability)  Lời giải, hay thuật toán, để giải bài toán  Lớp các bài toán không giải được (và sẽ không bao giờ giải được, dù với sự tiến bộ của công nghệ thông tin trong tương lai)  Nghiên cứu lý thuyết cách giải các bài toán  Mô hình tính toán ?  Độ phức tạp tính toán ?  Tính quyết định 9/56 Đâu là giới hạn của Tin học ?  Giới hạn của Vật lý :  Không tồn tại chuyển động vĩnh cửu vì : Mâu thuẫn với các định luật về nhiệt động lực học Chuyển động vĩnh cửu (Perpetual Motion) là chuyển động không ngừng, không cần tiêu tốn năng lượng 10/56 Những chủ đề chính của Tin học lý thuyết  Nghiên cứu các mô hình tính toán :  Các ngôn ngữ hình thức (Formal Languages)  Các ôtômat hữu hạn (Finite Automaton)  Máy Turing (Turing Machine)  Các hàm đệ quy (Recursive Functions)  Máy RAM (Random Access Memory Machine)  Độ phức tạp tính toán (Computational Complexity)  Mật mã học (Cryptology)  Và các hướng nghiên cứu mới trong lý thuyết tính toán  Mối quan hệ giữa các mô hình tính toán khác nhau  Cơ sở để thiết kế MTĐT (phần cứng) và thuật toán (phần mềm) trong hiện tại và tương lai 11/56 Chương mở đầu : cơ sở của môn học  Một số kiến thức Toán học cơ sở  Bảng chữ và câu  Khái niệm ngôn ngữ  Máy trừu tượng  Vấn đề biểu diễn ngôn ngữ 12/56 Một số kiến thức Toán học cơ sở  Lôgích học  Tập hợp, quan hệ  Ánh xạ và hàm  Tính đếm được của các tập hợp vô hạn  Đồ thị và cây  Phép chứng minh quy nạp  Các cấu trúc rời rạc 313/56 Bảng chữ và câu  Bảng chữ (alphabet) :  là một tập hữu hạn các ký tự (characters), hay ký tượng/ ký hiệu (symbol), ký hiệu bởi chữ cái Hy lạp   Kích thước của bảng chữ là số phần tử của bảng chữ đó, ký hiệu ||, hay Card() (Cardinality)  Ví dụ một số bảng chữ  : { # } | = 1 { 0, 1 } || = 2 { , , ,  } || = 4 {0, 1, 2, ... , 9} Chữ số thập phân, || = 10 {I, V, X, L, C, D, M} Chữ số La Mã {aA, bB, cC, ... , zZ} Chữ cái La tinh {, , , ... , } chữ cái Hi Lạp Bảng mã ASCII Các nét viết chữ Hán 14/56 Câu trên bảng chữ   Cho trước một bảng chữ  nào đó  Một câu (phrase, word), hay xâu (string), trên  :  là một dãy hữu hạn các phần tử của , ký hiệu bởi w (hay x, y, u, v...)  Độ dài của một câu là số ký tự có mặt trong câu, ký hiệu là |w| hay length(w)  Độ dài câu là hữu hạn, nhưng không hạn chế là có bao nhiêu ký tự  Một câu có thể có từ 0 đến n ký tự tuỳ ý  Câu có độ dài bằng 0 được gọi là câu rỗng (empty word), ký hiệu , hoặc e, hoặc  hoặc  15/56 Ví dụ về câu trên bảng chữ   Ví dụ Bảng chữ  Câu trên  { 0, 1 } , 0, 1, 00, 01, 10, 11, 100... { a....z } a, ab, zt, computer { 0, ..., 7, , , ,  } 432, 1234,  ASCII Một chương trình C, Pascal, Java, VB...  Cho một câu w có có |w|=n, người ta có thể trích ra từ w một ký tự nào đó có vị trí xác định trong phạm vi 1..n  Ví dụ câu w=aaabbaabbba có |w|=11, có thể trích ra các ký tự :  w(1) = a, ..., w(4) = b, ..., w(11) = a 16/56 Phép ghép tiếp các câu  Cho hai câu u và v trên   Phép ghép tiếp (Concatenation) của u và v là câu w = uv  Nghĩa là câu w gồm hai phần : u đgl là tiền tố (prefix)  rồi đến v là hậu tố (postfix) của w  Trường hợp câu w = xuy là ghép tiếp của ba câu x, u, y, u đgl trung tố (infix) của w  Người ta còn gọi câu rỗng  là câu đơn vị vì có w = w = w với w là một câu bất kỳ trên  Returning 17/56 Các phép toán khác trên xâu  Cho các câu w trên   Phép Đảo ngược (Reversion) một câu w, ký hiệu wR :  Là câu w được viết theo thứ tự ngược lại  Rõ ràng R =   wR = w đgl câu đối xứng : OMO, akitOMOtika...  Phép Lũy thừa (power) xâu  wn = www (n lần)  w0 =  với mọi w Quy ước chỉ định một câu (denotation) ỉ ị i 18/56 Khái niệm ngôn ngữ  Một ngôn ngữ hình thức (nói gọn ngôn ngữ) :  là tập hợp các câu được xây dựng trên cùng một bảng chữ đã cho   Ví dụ :  * là ngôn ngữ gồm tập tất cả các xâu trên bảng chữ  kể cả xâu rỗng  + là ngôn ngữ gồm tập tất cả các xâu trên bảng chữ  KHÔNG CÓ xâu rỗng  + = * -    là ngôn ngữ trống (tập trống)  Ví dụ  L1 = {a, ab, abb, bba, bbb} là ngôn ngữ hữu hạn trên {a, b}  L2 = {(ab)n | n > 0} là ngôn ngữ vô hạn trên {a, b} Chú ý {}   Chú ý : Người ta dùng phép “hình thức” (Fomal) để đối lập với “tự nhiên (Natural) i t ì t l i l i t i l t r 419/56 Máy trừu tượng (machine)  Mô hình IPO : nhận dữ liệu vào (data) và cho kết quả ra (result)  Hai cách nhìn :  Cách nhìn chức năng (functional look)  Cách nhìn cấu trúc (structural look)  Phân biệt các kiểu máy trừu tượng (machine type) theo bản chất của kết quả tính toán Máy Dữ liệu vào Dữ liệu ra 20/56 Chức năng đoán nhận câu Máy đoán nhận câu :  Giả sử dữ liệu vào w*, kết quả ra r{0, 1}, hay {False, True }  Tập hợp câu vào w đgl ngôn ngữ (language)  Có ba khả năng cho kết quả : 1. True hoặc False 2. Một kết quả khác 3. Không cho kết quả nào  Hai tập hợp câu vào ứng với hai khả năng đầu là bù nhau nếu máy cho kết quả cho mọi dữ liệu vào 21/56 Chức năng tính toán Máy tính toán (computation machine)  Giả sử dữ liệu vào w*, kết quả ra là một câu r trên một bảng chữ  nào đó  Khi đó, máy thực hiện tính hàm f từ * vào * : f : *  * Nghĩa là w  *, f(w)  *  Hàm f được gọi là hàm toàn phần (partial function) nếu với mọi câu vào w*, máy đều cho kết quả f(w)*  Người ta cũng nói kiểu máy đoán nhận chỉ là trường hợp đặc biệt của kiểu máy tính 22/56 Cách nhìn cấu trúc (structural look) Máy được xác định bởi một tập hữu hạn các phép toán Mỗi phép toán mô tả một phần cấu trúc của máy Phép toán sơ cấp (elementary operation) là phép toán nhỏ nhất (không chia cắt nhỏ hơn) Máy thực hiện (execution) mỗi phép toán trong một khoảng thời gian hữu hạn và xác định Chương trình (program) là tập hợp các phép toán sơ cấp để giải một bài toán nào đó Một tính toán (computation) là việc thực hiện lần lượt các phép toán sơ cấp theo một thứ tự xác định trước 23/56 Mô hình tính toán  Định nghĩa các lớp máy có cùng nguyên lý hoạt động  Thay đổi chương trình để giải bài toán trên cùng một máy mà không thay đổi máy giải  Mô hình tính toán (computation model), ký hiệu T là sự mô tả :  tất cả các phép toán sơ cấp  những đối tượng nào có thể tác động phép toán  cách thực hiện chương trình trên máy  Một trường hợp riêng (instance) của mô hình là máy cụ thể Mô hình + Chương trình = Máy  Mô hình tính toán T được gọi là một Tmáy 24/56 Một số thuật ngữ  Làm sao để có thể biết :  Lớp ngôn ngữ đoán nhận được (recognized), hay Tnhận biết được ?  Lớp các hàm tính được (computable) hay Ttính được ?  Lớp các ngôn ngữ liệt kê được (enumerable) hay Tliệt kê được ?  So sánh hai mô hình : T1 mạnh hơn T2 khi : Nếu T2 nhận biết được (tính được, liệt kê được) thì T1 cũng nhận biết được (tính được, liệt kê được)  T1 và T2 tương đương (equivalent) nếu T1 mạnh hơn T2 và ngược lại  T1 và T2 là không thể so sánh với nhau được nếu không tồn tại mô hình nào ít ra đủ mạnh hơn mô hình kia 525/56 Khái niệm bài toán (problem)  Một bài toán là :  Mô tả cách biểu diễn (hữu hạn) các phần tử của một tập hợp hữu hạn hay vô hạn đếm được  Một phát biểu liên quan đến các phần tử của tập hợp này  Kết quả có thể đúng, hoặc sai, tùy việc chọn phần tử  Bài toán trong Tin học lý thuyết :  Khác với khái niệm bài toán thông thường trong Toán học  Khác với bài toán hiểu theo nghĩa thông dụng 26/56 Một số ví dụ bài toán (1) Bài toán 1 :  Dữ liệu: Một số nguyên viết trong hệ 10  Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Bài toán 2 :  Dữ liệu : Một số nguyên viết trong hệ 10  Câu hỏi : Số nguyên này được viết dưới dạng tổng của 4 số bình phương ? Bài toán 3 :  Dữ liệu : Một số nguyên viết dưới dạng tích của các số hạng trong hệ 10  Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Bài toán 4 :  Dữ liệu : Một đồ thị hữu hạn G được biểu diễn bởi một danh sách các đỉnh và các cung, mỗi đỉnh được biểu diễn bởi một số nguyên trong hệ 10  Câu hỏi : Có tồn tại đường đi Hamilton (đi qua hết tất cả các đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần) trong đồ thị đã cho không ? 27/56 Một số ví dụ bài toán (2) Bài toán 5 :  Dữ liệu : Một biểu thức chính quy (regular expression) được xây dựng trên một bảng chữ  (là một biểu thức nhận được từ các câu w* bởi các phép hoặc, phép ghép tiếp, phép * và lấy bù)  Câu hỏi : Có phải biểu thức đã cho chỉ định ngôn ngữ trống (empty language) ? Bài toán 3n+1 (bài toán dừng) : chưa có câu trả lời về tính dừng function threen(n: integer): integer;{ recursive } begin if (n = 1) then 1 else if odd(n then threen(3*n+1) else threen(n div 2); end; 28/56 Bài toán tương ứng Post (Post’s correspondence problem) Dữ liệu : Một dãy hữu hạn các cặp câu (u1, v1), (u2, v2)..., (uk, vk) Câu hỏi : Tồn tại hay không một dãy chỉ số i1 , i2 ,...in sao cho thoả mãn ui1 ui2... uin = vi1 vi2... vin ? Ví dụ : cho * = {a, b, c } Và dãy các cặp câu : {(ab, aba), (ab, ba), (bab, ba), (ab, bab) } Cho câu : babababab Tồn tại dãy chỉ số {3 , 2, 2, 4} sao cho thoả mãn : bab.ab.ab.ab = ba.ba.ba.bab 29/56 Một số khái niệm khác  Kết hợp bài toán P với ngôn ngữ đặc trưng (characteristic language) LP* Ngôn ngữ LP = { w D * |  lời giải f(w) = true }  Bài toán ngược CP nhận được từ P bằng cách :  giữ nguyên cách biểu diễn các dữ liệu  đặt ngược lại câu hỏi Ngôn ngữ LCP = { w D * | Không  lời giải, hay f(w) = false } Ví dụ : Bài toán 1’ :  Dữ liệu : Cho một số nguyên viết trong hệ 10  Câu hỏi : Số nguyên này không phải là một số nguyên tố ?  Máy giải (solve) bài toán P nếu và chỉ nếu :   w *, máy cho phép xác định, trong một khoảng thời gian hữu hạn, nếu w LP hay w LCP  Phân lớp các bài toán tùy theo độ phức tạp (complexity)  Một bài toán là tầm thường (trivial) nếu LP =  hoặc nếu LCP =  * LP 30/56 Các phép toán trên ngôn ngữ  Ngôn ngữ là một tập hợp do đó có thể áp dụng các phép toán trên tập hợp :  Đối với các phần tử :  Đối với ngôn ngữ :  Cho L1, L2 và L là các ngôn ngữ, các phép toán:  Phép hợp L1  L2 = {w | w  L1 hoặc w  L2}  Phép giao L1  L2 = {w | w  L1 và w  L2}  Phép hiệu L1 – L2 = {w | w  L1 và w  L2}  Phép bù  L’ = {w | w  L} hoặc L’ = * - L          L2L1 L 631/56 Các phép toán trên ngôn ngữ  Phép ghép nối :  L1L2 = = {w | w = uv, u  L1 và v  L2}  Phép nghịch đảo :  LR = {w | wR  L}  Phép lũy thừa :  Ln = LLL (n lần)  Li = LLi-1 = Li-1L với i>0  L0 = {}  Ví dụ :  Cho L = { tic, tac, toe } khi đó :  L2 = LL = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe } Ghép nối L1 có m câu, và L2 có n câu, được ngng có ??? câum.n Là bản số của tích ĐêCac (Cartesian Product) í i 32/56 Các phép toán trên ngôn ngữ  Phép bao đóng (closure) :  L* = L0  L1   Ln  =  Phép bao đóng dương :  L+ = L1  L2   Ln  =  Nhận xét :  L+ = LL* = L*L  L* = L+  {  }  Ví dụ :  Cho L = { tic, tac, toe } khi đó :  L* = { , tic, tac, toe, tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe, tictictic, tictictac, ... }    0i iL   1i iL Khái niệm hữu hạn, vô hạn được hiểu như thế nào ? •Liên quan đến các phần tử của một tập hợp : khái niệm đếm (liệt kê) được •Người ta đặt song ánh các phần tử với số tự nhiên  •hữu hạn ? tập hợp có n phần tử, nK<, bị chặn trên •vô hạn ? tập hợp có n phần tử tuỳ ý, không bị chặn trên i i , i t i t t t : i i li t i t t t i t i t t , , ị t t t t , ị t 33/56 Ví dụ khác về ngôn ngữ  Cho  = {0..9}  { ., +, - }, xay dựng các lớp số :  Mọi câu trên là ghép tuỳ ý các chữ số 0..9, ., +, - tuy nhiên chỉ ghi nhận (xét) những câu là số có nghĩa  Số tự nhiên  = {0, 1, 2, ..., i, i+1, ... } i0,    Số nguyên  = { ..., -3, -2, -1, 0, 1, 2, ... } |i|0,    Số hữu tỷ  = { ..., -2/2, -2/3, -1/2, 0, 1/2, 2/2, ... } |m/n|0,    Số vô tỷ  = { ..., ..., ... } =    { ..., ..., ... } 34/56 Các ngôn ngữ chính quy (NNCQ)   tập hợp các ngôn ngữ chính quy (Regular Languages) trên  :  Được định nghĩa dựa trên các ngôn ngữ sơ cấp và các phép toán hội ( : “nhặt ra”), ghép và đóng lặp *  Là tập hợp nhỏ nhất (chứa ít phần tử nhất) các ngôn ngữ thõa mãn các điều kiện sau : 1.   , {} 2. { a }   với a   3. Nếu A, B  , thì AB, A.B và A*    Rõ ràng  là tập hợp bé nhất do được xây dựng từ các tập sơ cấp , {  } và { a } bởi các phép hội, ghép và bao đóng 35/56 Ví dụ xây dựng tập NNCQ   Cho ={}, những phần tử-ngôn ngữ có ngay (tự có) :    , {}, {}   Những ngôn ngữ L được xây dựng kiểu quy nạp (đệ quy) :  Luật : Nếu A, B  , thì AB, A.B và A*    A={}, B= {}, AB={, }, A.B={}={}, B* = {, , , , ... n, ... }, n bất kỳ n>0  Vậy sau bước này ta có : , {}, {}, {}, ..., {, , , , ... n, ... }  Và cứ thế tiếp tục xây dựng  36/56 (1) Biểu thức chính quy (BTCQ)  Người ta sử dụng các biểu thức chính quy (Regular Expressions) để biểu diễn các ngôn ngữ chính qui trên   Qui tắc xây dựng BTCQ trên  là các biểu thức được tạo thành theo các bước quy nạp như sau : 1. ,  và a, với mọi phần tử a của  đều là những BTCQ 2. Nếu  và  là hai BTCQ , thì (), (), ()* cũng là những BTCQ Chú ý 1 : Khi viết một BTCQ, có thể bỏ các dấu ngoặc đơn theo mức ưu tiên giảm dần : chẳng hạn viết a* thay vì (a)* Chú ý 2 : Có thể viết a+b thay vì viết ab Ví dụ, biểu thức ((0 (1*)) + 0) có thể viết 01*+ 0 i i , i i i ì i ì i í , i i 737/56 (2) Biểu diễn ngôn ngữ bởi biểu thức chính qui  Ngôn ngữ L() được biểu diễn (hay được chỉ định) bởi BTCQ  theo các bước quy nạp như sau : 1. L() = , L() = {  }, L(a) = { a } cho a  2. L((  )) = L()  L() 3. L(()) = L()L() 4. L(()*) = L()*  Từ (1) và (2) ta có tính chất sau : Một ngôn ngữ là chính qui nếu và chỉ nếu (nễu, khĩ ) ngôn ngữ đó được chỉ định bởi một biểu thức chính qui  Nhận xét :  Các BTCQ cũng tạo thành một ngôn ngữ vì chúng là những xâu ký tự trên bảng chữ  Đọc pxi 38/56 Bao đóng của bảng chữ   Cho bảng chữ , khi đó, L = { a | a   } là một NNCQ  Bao đóng của L là L* = * là một NNCQ có vô hạn câu  Có thể liệt kê hết (đếm được) tất cả các câu của *  Ví dụ * = (a + b)*  a b aa ab ba bb aaa aab aba abb baa bab bba bbb ...... ...... 1 2 3 4 5 6 7 8 ......  Cho  = {a, b} thì ta đã có một thứ tự tiền định a đứng trước b  Cho hai câu w1, w2 khi đó w1 đứng trước w2 khĩ |w1|| w2| , ì i ị i , i ĩ 39/56 Nghịch đảo câu xong thì cũng chính nó ! Đọc xuôi, đọc ngược như nhau Đứng bên tê, ngó bên ni, cũng rứa Đứng bên ni, ngó bên tê, cũng rứa Đi qua, đi lai, y chang ! Hai ký tự cách đều đầu và cuối câu y chang ! ị t ì í ! i, t , i, r i, t , r i , i l i, ! i t i ! Một số ví dụ _ 1  Cho bảng chữ  = { a, b }, có thể xây dựng được một số NNCQ trên  như sau : L1 = {, a, aa, aab } L1 có 4 câu L2 = { w  * | |w|  8 } L2 gồm các câu có độ dài  8 L3 = { w  * | |w| là một số lẻ } L3 gồm các câu có độ dài lẻ L4 = { w  * | na(w) = nb(w) } = {, ab, ba, aabb, abab, baab, ... } L4 gồm các câu có số chữ a đúng bằng số chữ b L5 = { w  * | w = wR } = {, aa, bb, aba, bab, abba, baab, ... } L5 gồm các câu đối xứng (palindrome) Có thể có thêm các nhận xét gì về các câu đối xúng ? t t t ì i 40/56 Ví dụ về một thuật toán kiểm tra câu đối xứng Func PalinCheck(w: string): bool OK = true; i=1, l=len(w) if l>0 then while OK and i<=l and w(i)=w(l) do i++; l-- Return OK w1 w2 wl-1 wl... i++ l-- 41/56 Một số ví dụ _ 2  Cho bảng chữ , a  , w  * và L  *  Khi đó :  ak = aa ... a k chữ a liên tiếp  wk = ww ... w ghép liên tiếp k câu w  k =  ...  = { w  * | |w| = k }  Lk = LL ... L ngôn ngữ gồm các câu là ghép k câu tuỳ ý của L  Trường hợp đặc biệt k = 0 :  a0 = w0 =   0 = L0 = {  }  Chú ý {  }   :  {  } có một câu là   còn  không có câu nào ! 42/56 Một số tính chất  Với quy ước L() là NNCQ đbdb BTCQ   Khi đó :  L() = L() khi và chỉ khi  =  Nghĩa là : Hai BTCQ bằng nhau cùng biểu diễn một NNCQ  Để chứng minh rằng hai tập hợp A và B đã cho là bằng nhau A = B cần chỉ ra AB và BA Nghĩa là cần CM hai chiều “” và “” 843/56 Một số ví dụ _ 3  Chứng minh rằng :  Các BTCQ : (a*b)*  (b*a)* và * cùng chỉ định một ngôn ngữ chính qui ?  Bằng cách “cùng L hai BTCQ” : L1 = L((a*b)*  (b*a)*) và L2 = L((a  b)*) = L(*) với  = { a, b } Cần CM rằng L1 = L2?  Từ nay về sau để đơn giản, ta viết w thay vì wL()  Lời giải là CM hai chiều “” và “” : “” : Rõ ràng L1 = (a*b)*(b*a)*  L2 = *, vì * là bao đóng “” : Để chứng minh điều ngược lại, ta xét một câu : w = w1w2...wn  * Cần chứng minh w  (a*b)*(b*a)* 44/56 a*b (a*b)* a*b (a*b)* Chứng minh w  (a*b)*(b*a)*  Giả sử w = w1w2...wn  * Xảy ra bốn trường hợp như sau : 1. w = an, do đó w  ( a )*  ( b*a )*  (a*b)*(b*a)* 2. w = bn, do đó w  ( b )*  ( a*b )*  (a*b)*(b*a)* 3. w chứa a và b, kết thúc bởi b. Ta có : w = a . . . ab b . . . b a . . . ab b . . . b Do đó, w  (a*b)*(b*a)* 4. w chứa a và b và kết thúc bởi a. Tương tự trường hợp 3, ta cũng có : w  L((a*b)*(b*a)*) 45/56 Các ngôn ngữ phi chính qui  Nhận xét :  Các BTCQ là vô hạn đếm được  Các BTCQ chỉ biểu diễn tập vô hạn đếm được NNCQ, nhưng không biểu diễn hết mọi ngôn ngữ  Tồn tại những ngôn ngữ phi chính qui và không có đủ các BTCQ để biểu diển mọi ngôn ngữ  Mọi ngôn ngữ không thể là chinh qui :  Tập hợp các ngôn ngữ và tập hợp các tập hợp con của một tập hợp đếm được (tập hợp các câu) là không đếm được  Tập hợp các NNCQ là đếm được vì mỗi NNCQ được biểu diển bởi một BTCQ và tập hợp các BTCQ là đếm được  Sẽ có nhiều ngôn ngữ khác với NNCQ 46/56 Có vô hạn không đếm được ngôn ngữ  = { a, b } * = { a, b }* Tập các NNCQ  Các ngôn ngữ phi CQ  Có 2n tập hợp con của một tập hợp A có n phần tử  Nếu A có vô hạn đếm được phần tử thì 2A có vô hạn không đếm được phần tử t t t t t t ì t 47/56 Ví dụ tập con  Cho A = { cục, cọ, cẫng) Hỏi có bao nhiêu tập hợp con của A ?  Trả lời : có 2|A|=23 = 8 tập hợp con của A  Đó là các tập hợp con : { rỗng, {cục} , {cọ} , {cẫng}, {cục , cọ}, {cục , cẫng } , {cọ,cẫng}, {cục, cọ, cẫng} }  Lý thuyết số  , ,  vô hạn đếm được  vô hạn không đếm được (lấp đầy trục số)  Dựng bằng compa-êke số - 0 1 2 ... + 2 2 48/56 Vấn đề biểu diễn ngôn ngữ  Một ngôn ngữ trên bảng chữ  là tập hợp con của +  Cho L+, làm sao để biểu diễn hết mọi câu wL ? Khi L có hữu hạn câu, chỉ việc liệt kê các câu Khi L có vô hạn câu, không thể liệt kê hết các câu của L, mà phải tìm cách biểu diễn hữu hạn :  Nếu L gồm các câu có một số tính chất nhất quán P nào đó, dùng tân từ để biểu diễn tính chất P đó L = { w* | P(w) }  Nếu L là NNCQ, sử dụng BTCQ  chỉ định L : L = L()  L tuỳ ý, không phải là NNCQ : sử dụng ôtômat và văn phạm - Ôtômat đoán nhận câu của một ngôn ngữ - Văn phạm sản sinh ra câu cho một ngôn ngữ Chi rứa ? 949/56 Ví dụ biểu diễn ngôn ngữ  Ngôn ngữ có vô hạn câu :  L1 = { ai  i là một số nguyên tố }, hay = { a2, a3, a5, a7, , a11, a13, }  L2 = { aibj  i  j  0 }, hay = { , a, ab, aab, aabb, } là ngôn ngữ gồm các câu có một dãy con a rồi đến một dãy con b, trong đó số con a bên trái nhiều hơn hoặc bằng số con b bên phải  L3 = (ab)* = { , ab, abab, ababab, } là ngôn ngữ gồm các câu có các cặp ab tuỳ ý (0..n cặp) 50/56 Ví dụ sản sinh ra câu của ngôn ngữ  Cho L là ngôn ngữ trên { a, b } được định nghĩa như sau : 1.   L 2. Nếu w  L thì awb  L 3. L không còn câu nào khác nữa (ngoài 1 và 2)  Qui luật sản sinh các câu của L như sau :  Từ (1), L = {  } Coi  là w, từ (2), ta có câu awb = ab = ab, L = { , ab }  Lại do (2), ta có L = { , ab, aabb, aaabbb, ... }  Cứ thế, ta có mọi câu của L có dạng aibi  i  0  Có thể biểu diễn L dưới dạng :  L = { aibi  i  0 } 51/56 Ví dụ đoán nhận một câu của ngôn ngữ  Giả sử định nghĩa ngôn ngữ L gồm các câu w :  Có thể thu gọn w về câu rỗng  : w    Thu gọn bằng cách thay thế dần các xâu con ab của w bởi   Ví dụ :  w = ab  L vì : ab    w = aabbab  L vì : aabbab  abab  ab    Coi a, b lần lượt là cặp dấu ngoặc đơn ( và ) :  L gồm các cặp dấu ngoặc đơn cân bằng nhau không cài nhau thu được từ một biểu thức toán học nào đó  Ví dụ, từ biểu thức (3*(x  y))  (x + 1), thực hiện bỏ hết các ký hiệu toán tử và toán hạng, ta nhận được câu ngoặc đơn cân bằng (())(), là câu aabbab 52/56 Bài tập 1 1. r + s = s + r 2. r + (s + t) = (r + s) + t 3. r (s + t) = rs + rt 4. r = r = r 5. r +  = r 6. ( + r)* = r* 7. r = r =  8. (r*)* = r* 9. r + r = r 10. r(st ) = (rs)t 11. * =  12. (r*s*)* = (r + s)* 13. r + r* = r* 14. (r + s)t = rt + st Cho các biểu thức chính qui r, s, t, trong đó nếu r = s thì có nghĩa L(r) = L(s) Chứng minh các tinh chất sau (dấu + ~ dấu ): 53/56 Bài tập_2 2. Tìm các BTCQ chỉ định phần bù của các ngôn ngữ sau :  (ab)*b  ((ab)(ab))* 3. Cho ngôn ngữ L trên bảng chữ { a, b } được định nghĩa như sau :    L  Nếu w  L thì awb  L  Nếu w  L thì bwa  L  Nếu w1, w2  L thì w1w2  L Chứng minh bằng quy nạp rằng : ngôn ngữ L theo cách định nghĩa trên khĩ L gồm mọi câu có số chữ a đúng bằng số chữ b (viết gọn na(w) = nb(w) ? Phép CM quy nạp (induction) : •Cần CM P(n), n  ? •Thử trường hợp P(0), P(1) •Giả sử P(n) đúng Cần CM rằng P(n+1) đúng i i i 54/56 Phép chứng minh Mệnh đề Pitagore: a2+b2=c2i Tiên đề/Định đề (công nhận) i ị Bổ đềĐịnh lýị lHệ quả Trời sinh ra thế !i i 10 55/56 CM r + s = s + r  “L” hai vế, cần CM rằng L(r + s) = L(s + r) :  Thật vậy, biến đổi vế trái : L(r + s) = (theo đn) = L(r)  L(s) = {w  * | w  L(r)  w  L(s) } = {w  * | w  L(s)  w  L(r) } (không tin, lập bảng chân lý) = L(s + r) (đpcm) (Qed-Quote Erat Demonstandum)  56/56 CM (r*s*)* = (r + s)*  Sử dụng định nghĩa ngôn ngữ L* để CM :  Đặt L1= (r*s*)*, L2 = (r + s)*, CM L1= L2 bằng cách CM L1 L2 và L2  L1  L1 L2 là hiển nhiên vì L2 là một bao đóng chưá mọi câu từ các BTCQ r và s  L2  L1 ? Theo đn L1={w|k: wkr*s*, w= w0w1 ... wk} Cho w L, CM wL1 w = r* = r* ()  r* s* w = s* = () s*  r* s* w = r*s*  r* s** = L1 r, s