Bài giảng Tin học lý thuyết - Chương 2 Ngôn ngữ và sự phân cấp Chomsky

Ngôn ngữ và sự phân cấp ChomskyNội dung:Khái niệm ngôn ngữCách biểu diễn ngôn ngữVăn phạmSự phân lớp văn phạmChương 2:1Ký hiệu, bộ chữ cái, chuỗiKý hiệu (symbol): là một thực thể trừu tượng mà ta không định nghĩa được một cách hình thứcCác chữ cái a, b, c hoặc các số 1, 2, 3 Bộ chữ cái (alphabet): ΣLà một tập (không rỗng) các ký hiệu nào đóBộ chữ cái Latin {A, B, C, , a, b, c, , z}Chuỗi (string): một chuỗi (hay một từ - word) trên bộ chữ cái ΣLà một dãy hữu hạn các ký hiệu của ΣMột ký hiệu có thể xuất hiện nhiều lần2ChuỗiĐộ dài chuỗi: là số các ký hiệu tạo thành chuỗi|abca| = 4Chuỗi rỗng: ký hiệu ε, là chuỗi không có ký hiệu nào|ε| = 0Chuỗi con: chuỗi v là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w.Chuỗi 10 là chuỗi con của chuỗi 010001Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗiChuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗiChuỗi abc có các tiền tố a, ab, abcChuỗi 0246 có các hậu tố 6, 46, 246, 02463ChuỗiChuỗi nối kết (ghép): là chuỗi được tạo thành bằng cách viết chuỗi thứ nhất, sau đó viết chuỗi thứ hai, ... Nối ghép của chuỗi Long và Int là LongInt Nối kết của chuỗi rỗng: εw = wε = w (với mọi w) → ε là đơn vị của phép nối kếtChuỗi đảo ngược: của chuỗi w, ký hiệu wR, là chuỗi w được viết theo thứ tự ngược lại. w = abcd → wR = dcba εR = ε4Ngôn ngữ (Languages)Tổng quan về ngôn ngữ:Ngôn ngữ tự nhiên: tiếng Việt, tiếng Anh, Ngôn ngữ lập trình: Pascal, C/C++, Là tập hợp các câu theo cấu trúc quy định nào đóBiểu thị các ý nghĩ, các sự kiện hay các khái niệmBao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng5Ngôn ngữ (Languages)Một ngôn ngữ (hình thức) L là một tập hợp các chuỗi của các ký hiệu từ một bộ chữ cái  nào đó. * và +: * : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng ε, sinh ra từ bộ chữ cái .+ : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi rỗng ε, sinh ra từ bộ chữ cái . * = + + {ε} + = * - {ε} = {0,1} thì: * = {ε, 0, 1, 00, 01, 10, 11, 000, } + = {0, 1, 00, 01, 10, 11, 000, } Chuỗi 010210  * vì có số 2  6Phép phần bù (complement): = * - LPhép nối kết (concatenation): L1L2 = {w1w2 | w1  L1 và w2  L2} trên bộ chữ cái Σ1  Σ2LLLLL = Li (kết nối i lần trên cùng ngôn ngữ L)L0 = {ε}Các phép toán trên ngôn ngữL7Phép bao đóng (closure): thành lập một ngôn ngữ bằng cách kết nối các chuỗi (với số lượng bất kỳ) các chuỗi của một ngôn ngữ L cho trướcBao đóng Kleene: L* =  LiBao đóng dương (positive): L+ =  LiChú ý: L+ = L*L = LL* L* = L+  {ε}Ví dụ: cho L = {a, ba}L2 = {aa, aba, baa, baba}L3 = {aaa, aaba, abaa, ababa, baaa,baaba, babaa, bababa}L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, }Các phép toán trên ngôn ngữi = 0i = 18Biểu diễn ngôn ngữLiệt kê chuỗi: L = {aa, aba, baa, baba}Mô tả đặc điểm chủ yếu: L = {ai | i là số nguyên tố}Biểu diễn thông qua văn phạm và automata:Cho phép biểu diễn ngôn ngữ một cách tổng quátVăn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữAutomata: cơ chế cho phép đoán nhận một chuỗi bất kỳ có thuộc một ngôn ngữ L hay không9Định nghĩa văn phạmTheo từ điển, văn phạm là một tập các quy tắc về cấu tạo từ và các quy tắc về cách thức liên kết từ lại thành câuĐịnh nghĩa: văn phạm cấu trúc G là một hệ thống gồm 4 thành phần G(V, T, P, S)V (variables): tập các biến (VD: A, B, C, )T (terminal): tập các ký hiệu kết thúc (V  T = Ø) (VD: a, b, c, , w, x, y, ...)P (production): tập luật sinh, dạng α→β với α, β  (V  T)*S (start): ký hiệu bắt đầu (S  V)10Định nghĩa văn phạmDẫn xuất trực tiếp: nếu α→β là một luật sinh thì       Dẫn xuất gián tiếp: nếu các chuỗi 1, 2, ...., m  * và 1  2, 2  3, ..., m-1  m thì m có thể được dẫn xuất từ 1 1 * mNgôn ngữ L sinh bởi văn phạm G:L (G) = {w  w  T * và S * w} Văn phạm tương đương: là 2 văn phạm sinh ra cùng một ngôn ngữ (G1 tương đương G2  L(G1)=L(G2) )11Phân cấp Chomsky trên văn phạmBằng cách áp đặt một số quy tắc hạn chế trên các luật sinh, Noam Chomsky đề nghị một hệ thống phân loại các văn phạm dựa vào tính chất của các luật sinh.Loại 0 – Văn phạm không hạn chế (Unrestricted Grammar): không cần thỏa điều kiện ràng buộc nào trên tập các luật sinhLoại 1 – Văn phạm cảm ngữ cảnh (CSG – Context Sensitive Grammar): nếu văn phạm G có các luật sinh dạng α→β và |β| ≥ |α|Loại 2 – Văn phạm phi ngữ cảnh (CFG – Context-Free Grammar): có luật sinh dạng A→α với A là một biến đơn và α là chuỗi các ký hiệu thuộc (V  T)*12Phân cấp Chomsky trên văn phạmLoại 3 – Văn phạm chính quy (RG – Regular Grammar): có mọi luật sinh dạng tuyến tính phải hoặc tuyến tính trái.Tuyến tính phải: A → wB hoặc A → wTuyến tính trái: A → Bw hoặc A → w Với A, B là các biến đơn, w là chuỗi ký hiệu kết thúc (có thể là rỗng)Nếu ký hiệu L0, L1, L2, L3 là các ngôn ngữ được sinh ra bởi văn phạm loại 0, 1, 2, 3, ta có:L3  L2  L1  L0 13Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S )Đây là văn phạm loại 3 (dạng tuyến tính phải)Một dẫn xuất từ S có dạng:S  aS  aaS  aaaA  aaabA  aaabbA  aaabbbA  aaabbbb = a3 b4  L(G) = a+b+ = {anbm | n,m ≥ 1}Các ví dụ về văn phạmS  aSS  aAA  bAA  b P = 14Ví dụ 2: văn phạm G( {S}, {a, b}, P, S )Đây là văn phạm loại 2 (dạng A→α )Một dẫn xuất từ S có dạng:S  aSb  aaSbb  aaaSbbb  aaaabbbb = a4b4  L(G) = {anbn | n ≥ 1}Các ví dụ về văn phạmS  aSbS  abP = 15Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S )Đây là văn phạm loại 1Một dẫn xuất từ S: S  aSBC  aaBCBC  aabCBC  aabBCC  aabbCC  aabbcC  aabbcc=a2b2c2  L(G) = {anbncn | n ≥ 1}Các ví dụ về văn phạmS → aSBCS → aBCCB → BCaB → abbB → bbbC → bccC → ccP = 16Định nghĩa ôtômát (automata)Định nghĩa: là máy trừu tượng có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữCon người phải lập trình sẵn cho máy một ‘lộ trình’ để thực hiệnBộ điều khiểnINPUTOUTPUTBỘ NHỚ17Phân loại automataAutomata đơn định (Deterministic Automata):Mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện tại (hàm chuyển của automata là đơn trị)Automata không đơn định (Non-deterministic Automata):Tại mỗi bước di chuyển, nó có vài khả năng để lựa chọn (hàm chuyển của automata là đa trị)18