Lý Thuyết Tính Toán - Tài Liệu, Ebook, Giáo Trình

• Trang chủ
• Đăng ký
• Đăng nhập
• Liên hệ

Thư Viện Tài Liệu, Ebook, Giáo Án, Bài Giảng

Thư viện tài liệu, giáo trình, giáo án, bài giảng, đồ án, luận văn tham khảo cho học sinh, sinh viên

Lý thuyết tính toán

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ề

10 trang | Chia sẻ: Mr Hưng | Lượt xem: 2012 | Lượt tải: 0 Nội dung tài liệu Lý thuyết tính toán, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên1Lý thuyết tính toán (Theory of Computation) PGS.TS. Phan Huy Khánh [email protected] 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

Các file đính kèm theo tài liệu này:

• lt3_ch1_modau_8571.pdf

Tài liệu liên quan

• Tạo trang web với HTML

  72 trang | Lượt xem: 1352 | Lượt tải: 0

• Tìm hiểu tông quan về CCS và cách tạo một Project trong CCS

  32 trang | Lượt xem: 5162 | Lượt tải: 1

• Hình học tính toán

  19 trang | Lượt xem: 1292 | Lượt tải: 0

• Lập trình Windows Phone - Module 4 – Bài 1, 2: Web Service

  12 trang | Lượt xem: 891 | Lượt tải: 0

• Quản trị mạng Microsoft Windows - Chứng thực và kiểm soát truy cập

  11 trang | Lượt xem: 2626 | Lượt tải: 0

• Bài giảng Kỹ thuật Lập trình - Chương 2: Mảng hai chiều - Trần Minh Thái

  33 trang | Lượt xem: 904 | Lượt tải: 0

• Dialog Box Common Controls Property Sheet

  106 trang | Lượt xem: 1596 | Lượt tải: 0

• Cuốn sách Nhập môn Hệ quản trị cơ sở dữ liệu DB2

  21 trang | Lượt xem: 1450 | Lượt tải: 0

• Hướng dẫn lập trình cơ bản với Android

  20 trang | Lượt xem: 1480 | Lượt tải: 1

• Cười té ghế với 20 bí mật thầm kín của Google

  11 trang | Lượt xem: 1498 | Lượt tải: 0

Copyright © 2025 ZUN.vn - Thư viện luận văn, Mẫu Đơn, Thư viện tài liệu tham khảo hay