Bài giảng Lý thuyết tính toán: Chương 1 - PGS.TS. Phan Huy Khánh

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

146
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 1 của bài giảng Lý thuyết tính toán trình bày một số kiến thức cơ sở của môn học như: 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ữ. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết tính toán: Chương 1 - PGS.TS. Phan Huy Khánh

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