Ngôn ngữ hình thức và Ôtômat - Chương 1 Mở đầu

Chia sẻ: Mmm Mmm | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

158
lượt xem 20
download

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

Học phần cung cấp cơ sở toán học của các phương pháp hình thức trong việc xây dựng các ngôn ngữ lập trình Giúp sinh viên hiểu được những yếu tố cơ bản của một ngôn ngữ hình thức như bảng chữ, từ vụng, cú pháp và ngữ nghĩa Học phần trình bày các công cụ chủ yếu để làm việc với các ngôn ngữ hình thức là văn phạm và ôtômat, phân loại ngôn ngữ của Chomsky :

Chủ đề:

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

Lưu

Nội dung Text: Ngôn ngữ hình thức và Ôtômat - Chương 1 Mở đầu

Chào mọi người ! Chà ườ Chào Ngôn ngữ hình thức và Ôtômat Hello Everyone! (Formal Language & Automata) Bonjour Tout le Monde ! PGS.TS. Phan Huy Khánh Khá 他好! khanhph@vnn.vn, phk@ud.edu.vn khanhph@vnn.vn, Chương 1 M ở đầ u Привет Kаждый ! 2/38 2/38 Ta sẽ học những buổi mô ? Trường ĐHSP : 05CTT12 Trườ (Hai lớp trưởng quyết định) : ưở Chiều thứ Hai hàng tuần, tại A5-104, 13H30 hà A5- Chi Những buổi đầu : Nh Chiều thứ Hai 14/01 Chi To Start… Sáng thứ Bảy, 26/01/2008, 7H00 Sau Tết, t.29, 13H30, 25/02/08 Sau “One picture is worth more than ten thousand words” Chinese Proverb 4/38 4/38 Ghi chép như thế nào ? ché Một vài “chuyện nhỏ” bắt đầu môn học và Có nên ghi bài giảng trên lớp vào sổ, vở học trò ? bà và Thủ tục “chào hỏi” : chà Th Học bằng slide cần có TLTK+ cách ghi hợp lý có cá Vào lớp muộn, hoặc ra khỏi lớp, không cần xin phépphé Nếu không sẽ xảy ra hiện tượng “THỪA TAY”, “để tay ở ượ TAY” Khi Giảng viên (GV) hỏi, cần : Khi nhà” nhà” Nói rõ và to giọng để cả lớp cùng nghe được và cù ượ Ghi bài giảng trên lớp vào giấy rời A4 Ghi bà và Khi trả lời, cần thực hiện ngay : Khi Từ chối, không biết, hoặc trả lời trực tiếp vào câu hỏi và Mỗi môn học một tập giấy A4, có màu đánh dấu phân biệt có Chuẩn bị học : Chu Nguyên tắc thao tác tiếp thụ tri thức và ứng dụng : tá và Nguyên Lớp sạch sẽ (mọi nghĩa), sẵn sàng cho buổi dạy sà Thu nhặt, liệt kê, vun xới Thu Ngồi tập trung gần tôi, không ngồi kiểu “gió đưa ao bèo...” gió bè ...” Ng Phân loại, sắp xếp Phân Giúp GV chuẩn bị màn hình, đèn chiếu, ổ cắm điện... Giú hì Khoanh vùng, giới hạn Khoanh vù Kết thúc môn học : thú Chỉ định, lựa chọn, tìm kiếm tì Ch Giúp GV dọn dẹp màn hình, đèn chiếu, ổ cắm điện... Giú mà hì Vận dụng, hoàn thiện, làm giàu tri thức hoà là già Tìm kiếm phương pháp học tập hiệu quả phá Phát huy các giác quan : mắtn, tain, miệngn, mũin, tayn ... Phá cá giá ... 5/38 5/38 6/38 6/38 1
Để có thể “tốc ký” ký” Mục đích môn học Dùng Sử dụng bảng viết tắt (BVT) : Học phần cung cấp cơ sở toán học của các phương pháp toá cá phá tự định nghĩa chữ viết tắt của riêng mình mì hình thức trong việc xây dựng các ngôn ngữ lập trình cá trì Ví dụ : ql = quản lý Giúp sinh viên hiểu được những yếu tố cơ bản của một Giú ượ pp = phương pháp phá ngôn ngữ hình thức như bảng chữ, từ vụng, cú pháp và cú phá và ngữ nghĩa pp+ = phân phối Học phần trình bày các công cụ chủ yếu để làm việc với trì bà cá = người... ng ườ các ngôn ngữ hình thức là văn phạm và ôtômat, phân loại là và Luôn mang BVT theo mình, mọi lúc mọi nơi mì lú Luôn ngôn ngữ của Chomsky : Chỉ chọn ghi các ý chính, hay từ khoá cá chí khoá Ch Ngôn ngữ chính quy chí Ngôn Không nhất thiết ghi cả câu Không Ngôn ngữ phi ngữ cảnh Ngôn Tìm mọi cách đễ vẽ, thay vì chỉ viết ! cá vì Ngôn ngữ cảm ngữ cảnh Ngôn Ngôn ngữ loại 0 (gần gũi với ngôn ngữ tự nhiên) Ngôn 7/38 7/38 8/38 8/38 Kiến thức yêu cầu Đánh giá kết quả học tập giá Môn học yêu cầu kiến thức tiên quyết : Toán cho Tin học Toá Môn Yêu cầu : Yêu Lý thuyết Lý Hiiểu nội dung trình bày trên lớp trì bà H Tập hợp Thực hiện các bài tập về nhà cá nhà Th Đồ thị Khả năng thực hành hà Kh Kỹ thuật chứng minh Tinh thần thái độ và năng lực học tập thá Tinh Qui nạp Nghe giảng, ghi chép ché Nghe Phản chứng Trả lời và đặt câu hỏi và Tr Kỹ thuật mô phỏng Tham khảo tài liệu, truy cập internet tà Georg Cantor (1845–1918) Tham Các kiến thức cần thiết khác : khá Founder of Modern Set Theory Tham gia học nhóm, tập thảo luận và thuyết trình nhó và trì Tham Cơ sở Lập trình trì … Môn học đòi hỏi một số kỹ năng : Môn Kiiểm tra giữa kỳ : Bài thi viết 15-30 phút Bà 15- phú K Khả năng đọc hiểu vấn đề Kh Kiiểm tra cuối kỳ : Bài thi viết 60-75 phút Bà 60- phú K Trình bày diễn đạt vấn đề (nghệ thuật !) Trì bà Khả năng thảo luận, làm việc theo nhóm... là nhó Kh 9/38 9/38 10/38 10/38 Nội dung môn học Tài liệu tham khảo Gặp cô Hương, văn thư khoa CNTT Giáo trình + Bài giảng trên lớp Giá trì Bà Chương 1 Mở đầu (chúng mình ?) Tài liệu Nguyễn Văn Ba, Ngôn ngữ hình thức, NXBKH&KT, 2002. Ba, Nguy Chương 2 Ôtômat hữu hạn (ôhh/ôh2/ô2h) SM. D. Davis, E. J. Weyuker, Computability, Complexity and Computability, SM. languages, Academic Press, 1983 Chương 3 Văn phạm chính qui (VPCQ) chí J. E. Hopcroft, J. D. Ulman, Introduction to Automata Theory, Theory, Introduction J. Languages and Computation, Addison - Wesley, 1979 Phan Huy Khánh. Lý thuyết ngôn ngữ hình thức và ôtômát ôtômá Chương 4 Ôtômat đẩy xuống (ôđx) (ô x) Lý Khá Phan Tài liệu lưu hành nội bộ hà Hồ Văn Quân. Giáo trình lý thuyết ôtômát và ngôn ngữ hình Quân. Giá trì ôtômá và Chương 5 Máy Turing (MT) thức. NXBĐHQG HCM, 2002 HCM, NXB A. Salomaa, Nhập môn tin học, lý thuyết tính toán và ôtômat. tí toá Nh A. NXB Khoa học Kỹ thuật, Hà nội 1992 Hà Internet: tìm kiếm Google.com.vn, wikipedia Internet: tì 11/38 11/38 12/38 12/38 2
Vài dòng lịch sử M ở đ ầu ☺ Chương 1 Cantor (1845-1918) Một số khái niệm khá “Nếu tôi có một số thành công nhất địịnh trong “Nếu tôi có một số thành công nhất đ nh trong Lý thuyết tập hợp toán học thì đó là vì tôi luôn thấy nó rất khó” Bảng chữ (Σ) toán học thì đó là vì tôi luôn thấy nó rất khó” Hilbert (1862-1943) Hilbert Hilbert Câu (xâu) Câu Toán học chặt chẽ Ngôn ngữ Ngôn Gödel (1906-1978) Mô tả ngôn ngữ Mô Lý thuyết về tính không đầy đủ Các phép toán (θ) trên ngôn ngữ (ng2) phé toá Church, Kleene, Post, Markov, von Neumann, Turing Biiểu thức chính qui (BTCQ) chí B CM từ đlý mô (Preuves de quels théorèmes)? CM với thtoán mô (Avec quels algorithmes)?ta thật ngắn “Tầm nhìn ta thật ngắn “Tầm nhìn Các ngôn ngữ phi chính qui chí mà đã thấy bao thứ để làm” mà đã thấy bao thứ để làm” Turing (1912-1954) Alan Turing Vấn đề biểu diễn ngôn ngữ Alan Turing Máy Turing McCulloch, Pitts Mạng nơ-ron nhân tạo Chomsky 13/38 13/38 14/38 14/38 Mô hình toán học mô tả ngôn ngữ - hình thức hoá ngôn ngữ Câu trên bảng chữ Σ Bảng chữ và câu Bảng chữ (alphabet) : Cho trước một bảng chữ Σ nào đó Cho ướ là một tập hữu hạn các ký tự (characters), hay ký tượng/ cá ượ Một câu (phrase, word), hay xâu (string), trên Σ : câu xâu ký hiệu (symbol), ký hiệu bởi chữ cái Hy lạp Σ là một dãy hữu hạn các phần tử của Σ, cá Kích thước của bảng chữ là số phần tử của bảng chữ đó, ướ ký hiệu bởi w (hay x, y, u, v...) ký hiệu |Σ|, hay Card(Σ) (Cardinality) Ví dụ một số bảng chữ Σ : Độ dài của một câu là số ký tự có mặt trong câu, là ký hiệu là |w| hay length(w) là {#} |=1 Độ dài câu là hữu hạn, là |Σ| = 2 { 0, 1 } nhưng không hạn chế là có bao nhiêu ký tự { ♣, ♠, ♦, ♥ } |Σ| = 4 Chữ số thập phân, |Σ| = 10 {0, 1, 2, ... , 9} Một câu có thể có từ 0 đến n ký tự tuỳ ý có {I, V, X, L, C, D, M} Chữ số La Mã Câu có độ dài bằng 0 được gọi là câu rỗng (empty word), Câu có ượ là {aA, bB, cC, ... , zZ} Chữ cái La tinh ký hiệu ε, hoặc e, hoặc λ hoặc ω {αΑ, βΒ, χΧ, ... , ζΖ} chữ cái Hi Lạp Bảng mã ASCII 15/38 15/38 16/38 16/38 Ví dụ về câu trên bảng chữ Σ Phép ghép tiếp các câu Phé ghé cá Cho hai câu u và v trên Σ và Ví dụ Cho Phép ghép tiếp (Concatenation) của u và v là câu w = uv Bảng chữ Σ Câu trên Σ Phé ghé và là Nghĩa là câu w gồm hai phần : Ngh là ε, 0, 1, 00, 01, 10, 11, 100... { 0, 1 } u đgl là tiền tố (prefix) là { a....z } a, ab, zt, computer ab rồi đến v là hậu tố (postfix) của w là { 0, ..., 7, ♠, ♣, ♦, ♥ } 4♣3♦2♠, 1234, ♣♠ ♣♠ ASCII Một chương trình C, Pascal, Java, VB... trì Trường hợp câu w = xuy là ghép tiếp của ba câu x, u, y, Trườ là ghé u, y, u đgl trung tố (infix) của w Cho một câu w có có |w|=n, người ta có thể trích ra từ w có |w|=n, ườ có trí Cho một ký tự nào đó có vị trí xác định trong phạm vi 1..n trí Người ta còn gọi câu rỗng ε là câu đơn vị đơ Ngườ vì có εw = wε = w Ví dụ câu w=aaabbaabbba có |w|=11, có với w là một câu bất kỳ trên Σ là có thể trích ra các ký tự : trí cá w(1) = a, ..., w(4) = b, ..., w(11) = a Returning 17/38 17/38 18/38 18/38 3
Các phép toán khác trên xâu phé toá khá Khái niệm ngôn ngữ Khá Một ngôn ngữ hình thức (nói gọn ngôn ngữ) : (nó Cho các câu w trên Σ Cho cá là tập hợp các câu cá Phép Đảo ngược (Reversion) một câu w, ký hiệu Phé ượ wR : được xây dựng trên cùng một bảng chữ đã cho Σ đượ cù Là câu w được viết theo thứ tự ngược lại ượ ượ Ví dụ : Rõ ràng εR = ε Rõ rà Σ* 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 wR = w đgl câu đối xứng : OMO, akitOMOtika... akitOMOtika... Σ+ 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 CÓ Phép Lũy thừa (power) xâu Phé Σ+ = Σ* - ε Chú ý {ε} ≠ ∅ ∅ là ngôn ngữ trống (tập trống) wn = ww…w (n lần) ww… Quy ước chỉ định một câu Ví dụ w0 = ε với mọi w (denotation) L1 = {a, ab, abb, bba, bbb} là ngôn ngữ hữu hạn trên {a, b} là L1 L2 = {(ab)n | n > 0} là ngôn ngữ vô hạn trên {a, b} là L2 19/38 19/38 20/38 20/38 Các phép toán trên ngôn ngữ phé toá Các phép toán trên ngôn ngữ phé toá Phép ghép nối : Phé ghé Ngôn ngữ là một tập hợp do đó có thể áp dụng các phép toán Ngôn cá phé toá trên tập hợp : L1L2 = = {w | w = uv, u ∈ L1 và v ∈ L2} và L1L2 ∈∉ Đối với các phần tử : cá Phép nghịch đảo : Phé ∩∪⊂⊆⊄⊃⊇ Đối với ngôn ngữ : ngôn LR = {w | wR ∈ L} Cho L1, L2 và L là các ngôn ngữ, các phép toán: và là cá phé toá Cho Phép lũy thừa : Phé Ghép nối L1 có m Phép hợp Phé Ln = LL…L (n lần) LL… câu, và L2 có n câu, L1 ∪ L2 = {w | w ∈ L1 hoặc w ∈ L2} L1 Li = LLi-1 = Li-1L với i>0 được ngng có m.n câu ??? Phép giao Phé L0 = { ε } L1 ∩ L2 = {w | w ∈ L1 và w ∈ L2} và L1 L2 L1 Là bản số của tích ĐêCac Là bản số của tích ĐêCac Ví dụ : Phép hiệu Phé (Cartesian Product) (Cartesian Product) Cho L = { tic, tac, toe } khi đó : tic, tac, toe Cho L1 – L2 = {w | w ∈ L1 và w ∉ L2} và L1 L2 = LL L Phép bù Phé bù = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe } toetac, L’ = {w | w ∉ L} hoặc L’ = Σ* - L L’ 21/38 21/38 22/38 22/38 Các phép toán trên ngôn ngữ phé toá Các ngôn ngữ chính quy (NNCQ) chí Phép bao đóng (closure) : Phé ℜ tập hợp các ngôn ngữ chính quy (Regular Languages) chí cá ngôn ∞ i UL L* = L 0 ∪ L 1 ∪ … ∪ Ln ∪ … = trên Σ : i= 0 Phép bao đóng dương : Phé Được định nghĩa dựa trên các ngôn ngữ sơ cấp Đượ cá ∞ i UL và các phép toán hội, ghép và đóng lặp * phé toá ghé và L + = L1 ∪ L 2 ∪ … ∪ L n ∪ … = i=1 Là tập hợp nhỏ nhất (chứa ít phần tử nhất) các ngôn ngữ cá Nhận xét : Nh xé thõa mãn các điều kiện sau : cá L+ = LL* = L*L 1. ∅ ∈ ℜ, {ε}∈ℜ L * = L+ ∪ { ε } 2. { a } ∈ ℜ với ∀a ∈ Σ Ví dụ : 3. Nếu A, B ∈ ℜ, thì A∪B, A.B và A* ∈ ℜ thì và Cho L = { tic, tac, toe } khi đó : tic, tac, toe Cho Rõ ràng ℜ là tập hợp bé nhất do được xây dựng từ các tập Rõ rà bé ượ L* = { ε, tic, tac, toe, tictic, tictac, tictoe, tactic, tactac, tactoe, sơ cấp ∅, { ε } và { a } bởi các phép hội, ghép và bao đóng và cá phé ghé và bao toetic, toetac, toetoe, tictictic, tictictac, ... } 23/38 23/38 24/38 24/38 4
Biểu thức chính quy (BTCQ) chí Biểu diễn ngôn ngữ bởi biểu thức chính qui chí Người ta sử dụng các biiểu thức chính quy (Regular chí cá b Ngôn ngữ L(ξ) được biểu diễn (hay được chỉ định) Ngườ đượ (hay ượ Ngôn Expressions) để biểu diễn các ngôn ngữ chính qui trên Σ cá chí bởi BTCQ ξ theo các bước quy nạp như sau : cá ướ Qui tắc xây dựng BTCQ trên Σ là các biểu thức được tạo ượ Qui 1. L(∅) = ∅, L(ε) = { ε }, L(a) = { a } cho ∀a ∈Σ ∈Σ thành theo các bước quy nạp như sau : thà cá ướ 2. L((α ∪ β)) = L(α) ∪ L(β) (2) 1. ∅, ε và a, với mọi phần tử a của Σ 3. L((αβ)) = L(α)L(β) đều là những BTCQ là 4. L((α)*) = L(α)* (1) 2. Nếu α và β là hai BTCQ , Từ (1) và (2) ta có tính chất sau : và có thì (α∪β), (αβ), (α)* cũng là những BTCQ thì là Một ngôn ngữ là chính qui nếu và chỉ nếu chí và ngôn ngữ đó được chỉ định bởi một biểu thức chính qui ượ chí Chú ý 1 : Khi viết một BTCQ, có thể bỏ các dấu ngoặc đơn BTCQ có Chú Chú các Nhận xét : Nh xé theo mức ưu tiên giảm dần : chẳng hạn viết a* thay vì (a)* vì Chú ý 2 : Có thể viết a+b thay vì viết a∪b Chú thay vì Có vì Các BTCQ cũng tạo thành một ngôn ngữ thà Ví dụ, biểu thức ((0 (1*)) + 0) có thể viết 01*+ 0 (1*)) + 0) có th Ví có vì chúng là những xâu ký tự trên bảng chữ Σ chú là 25/38 25/38 26/38 26/38 Bao đóng của bảng chữ Σ Một số ví dụ _ 1 Cho bảng chữ Σ = { a, b }, Cho Cho bảng chữ Σ, khi đó, L = { a | ∀a ∈ Σ } là một NNCQ khi là Cho có thể xây dựng được một số NNCQ trên Σ như sau : ượ nh Bao đóng của L là L* = Σ* là một NNCQ có vô hạn câu là là có Bao L1 = {ε, a, aa, aab } L1 có 4 câu Có thể liệt kê hết (đếm được) tất cả các câu của Σ* ượ L2 = { w ∈ Σ* | |w| ≤ 8 } L2 gồm các câu có độ dài ≤ 8 cá có Ví dụ Σ* = (a+ b)* ε 1 L3 = { w ∈ Σ* | |w| là một số lẻ } L3 gồm các câu có độ dài lẻ là cá có L4 = { w ∈ Σ* | na(w) = nb(w) } 2 3 b a = {ε, ab, ba, aabb, abab, baab, ... } ab, L4 gồm các câu có số chữ a đúng bằng số chữ b cá có 7 6 5 4 bb ab ba aa L5 = { w ∈ Σ* | w = wR } ... 8 = {ε, aa, bb, aba, bab, abba, baab, ... } aa, aaa aab aba abb baa bab bba bbb L5 gồm các câu đối xứng (palindrome) cá ... ... 27/38 27/38 28/38 28/38 Một số ví dụ _ 2 Một số tính chất Cho bảng chữ Σ, a ∈ Σ, w ∈ Σ* và L ⊆ Σ* và Cho Với quy ước L(α) là NNCQ đbdb BTCQ α là Khi đó : Khi Khi đó : Khi ak = aa ... a k chữ a liên tiếp L(α) = L(β) khi và chỉ khi α = β và L( wk = ww ... w ghép liên tiếp k câu w ghé Nghĩa là : là Σk = ΣΣ ... Σ = { w ∈ Σ* | |w| = k } ΣΣ Hai BTCQ bằng nhau cùng biểu diễn một NNCQ cù Lk = LL ... L ngôn ngữ gồm các câu là ghép k câu tuỳ ý của L cá là ghé Trường hợp đặc biệt k = 0 : Trườ Để chứng minh rằng hai tập hợp A và B đã cho là bằng nhau và là a0 = w0 = ε A=B Σ0 = L0 = { ε } cần chỉ ra A⊂B và B⊂A và Chú ý { ε } ≠ ∅ : Chú Nghĩa là cần CM hai chiều “⊂” và “⊃” { ε } có một câu là ε có là còn ∅ không có câu nào ! có nà còn 29/38 29/38 30/38 30/38 5
Chứng minh w ∈ (a*b)*∪(b*a)* Một số ví dụ _ 3 Chứng minh rằng : Ch Giiả sử w = w1w2...wn ∈ Σ* G L((a*b)* ∪ (b*a)*) = L((a ∪ b)*) = Σ* với Σ = { a, b } L((a*b)* Xảy ra bốn trường hợp như sau : ườ Nghĩa là các BTCQ : Ngh là 1. w = an, do đó w ∈ ( εa )* ⊂ ( b*a )* ⊂ (a*b)*∪(b*a)* do (a*b)* ∪ (b*a)* và Σ* và 2. w = bn, do đó w ∈ ( εb )* ⊂ ( a*b )* ⊂ (a*b)*∪(b*a)* do cùng chỉ định một ngôn ngữ chính qui chí 3. w chứa a và b, kết thúc bởi b. Ta có : và thú có w = a . . . ab b . . . b a . . . ab b . . . b ab Từ nay về sau để đơn giản, ta viết w ∈ α thay vì w ∈ L(α) vì a*b (a*b)* a*b (a*b)* Lời giải là CM hai chiều “⊂” và “⊃” : là (a*b)*∪(b*a)* Do đó, w ∈ “⊂” : Rõ ràng (a*b)*∪(b*a)* ⊂ Σ* vì Σ* là bao đóng rà vì là bao 4. w chứa a và b và kết thúc bởi a. và và thú “⊃” : Để chứng minh điều ngược lại, ta xét một câu : ượ xé Tương tự trường hợp 3, ta cũng có : ườ có w = w1w2...wn ∈ Σ* w ∈ L((a*b)*∪(b*a)*) Cần chứng minh w ∈ (a*b)*∪(b*a)* 31/38 31/38 32/38 32/38 Các ngôn ngữ phi chính qui chí Có vô hạn không đếm được ngôn ngữ ượ Nhận xét : Nh xé Σ = { a, b } Các BTCQ là vô hạn đếm được là ượ Các ngôn ngữ phi CQ 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 chí Tập các NNCQ ℜ cá và không có đủ các BTCQ để biểu diển mọi ngôn ngữ có 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 cá cá Σ* = { a, b }* tập hợp đếm được (tập hợp các câu) là không đếm được ượ cá là không ượ Tập hợp các NNCQ là đếm được vì mỗi NNCQ được biểu diển cá là ượ vì ượ bởi một BTCQ và tập hợp các BTCQ là đếm được và cá là ượ Có 2n tập hợp con của một tập hợp A có n phần tử Có 2n tập hợp con của một tập hợp A có n phần tử có Sẽ có nhiều ngôn ngữ khác với NNCQ khá 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ử 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ử có ượ thì ượ 33/38 33/38 34/38 34/38 Vấn đề biểu diễn ngôn ngữ Ví dụ 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 Σ+ Ngôn ngữ có vô hạn câu : Ngôn Cho L⊆Σ+, làm sao để biểu diễn hết mọi câu w∈L ? là Cho L1 = { ai ⏐ i là một số nguyên tố }, hay là Khi L có hữu hạn câu, chỉ việc liệt kê các câu Khi có cá = { a2, a3, a5, a7, …, a11, a13, … } Khi L có vô hạn câu, không thể liệt kê hết các câu của L, Khi có cá L2 = { aibj ⏐ i ≥ j ≥ 0 }, hay mà phải tìm cách biểu diễn hữu hạn : tì cá = { ε, a, ab, aab, aabb, … } Nếu L gồm các câu có một số tính chất nhất quán P nào đó, cá có quá nà 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, cá có dùng tân từ để biểu diễn tính chất P đó trong đó số con a bên trái nhiều hơn hoặc bằng số con b bên phải trá L = { w∈Σ* | P(w) } Nếu L là NNCQ, sử dụng BTCQ α chỉ định L : là L3 = (ab)* L = L(α) = { ε, ab, abab, ababab, … } L tuỳ ý, không phải là NNCQ : sử dụng ôtômat và văn phạm là và tu là ngôn ngữ gồm các câu có các cặp ab tuỳ ý (0..n cặp) cá có - Ôtômat đoán nhận câu của một ngôn ngữ oá - văn phạm sản sinh ra câu cho một ngôn ngữ 35/38 35/38 36/38 36/38 6
Ví dụ sản sinh ra câu của ngôn ngữ Ví dụ đoán nhận một câu của ngôn ngữ oá Giiả sử định nghĩa ngôn ngữ L gồm các câu w∈Σ∗ : cá Cho L là ngôn ngữ trên { a, b } được định nghĩa như sau : Cho là trên a, đượ G 1. ε ∈ L Có thể thu gọn w về câu rỗng ε : w ⇒ ε 2. Nếu w ∈ L thì awb ∈ L Thu gọn bằng cách thay thế dần các xâu con ab của w bởi ε thì cá cá Thu 3. L không còn câu nào khác nữa (ngoài 1 và 2) nà khá (ngoà và Ví dụ : Qui luật sản sinh các câu của L như sau : cá Qui w = ab ∈ L vì : ab ⇒ ε vì ab Từ (1), L = { ε } w = aabbab ∈ L vì : aabbab ⇒ abab ⇒ ab ⇒ ε vì aabbab Coi ε là w, từ (2), ta có câu awb = aεb = ab, L = { ε, ab } có Coi a, b lần lượt là cặp dấu ngoặc đơn ( và ) : ượ là và Coi Lại do (2), ta có L = { ε, ab, aabb, aaabbb, ... } có L gồm các cặp dấu ngoặc đơn cân bằng nhau không cài nhau cá cà Cứ thế, ta có mọi câu của L có dạng aibi ⏐ ∀i ≥ 0 có có thu được từ một biểu thức toán học nào đó ượ toá nà Có thể biểu diễn L dưới dạng : ướ Ví dụ, từ biểu thức (3*(x − y)) / (x + 1), thực hiện bỏ hết các 1), cá ký hiệu toán tử và toán hạng, ta nhận được câu ngoặc đơn toá toá ượ L = { aibi ⏐ ∀i ≥ 0 } cân bằng (())(), là câu aabbab (())(), là 37/38 37/38 38/38 38/38 7