Bài giảng Chương 2: Ngôn ngữ và sự phân cấp Chomsky
lượt xem 7
download
Mời các bạn cùng tìm hiểu khái niệm ngôn ngữ; cách biểu diễn ngôn ngữ; văn phạm; sự phân lớp văn phạm được trình bày cụ thể trong "Bài giảng Chương 2: Ngôn ngữ và sự phân cấp Chomsky".
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Chương 2: Ngôn ngữ và sự phân cấp Chomsky
- Chương 2: Ngôn ngữ và sự phân cấp Chomsky Nội dung: • Khái niệm ngôn ngữ • Cách biểu diễn ngôn ngữ • Văn phạm • Sự phân lớp văn phạm 1
- Ký hiệu, bộ chữ cái, chuỗi Ký 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ức • Cá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ần 2
- Chuỗi Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi • |abca| = 4 Chuỗi rỗng: ký hiệu ε, là chuỗi không có ký hiệu nào • |ε| = 0 Chuỗ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 010001 Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi Chuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗi • Chuỗi abc có các tiền tố a, ab, abc • Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 3
- Chuỗi Chuỗ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ết Chuỗ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 = ε 4
- Ngô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ệm • Bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng 5
- Ngô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 6
- Các phép toán trên ngôn ngữ Phép phần bù (complement): L= *-L Phép nối kết (concatenation): L1L2 = {w1w2 | w1 L1 và w2 L2} trên bộ chữ cái Σ1 Σ2 • LLL…LL = Li (kết nối i lần trên cùng ngôn ngữ L) • L0 = {ε} 7
- Các phép toán trên ngôn ngữ Phé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ước i Bao đóng Kleene: L* = L i=0 Bao đóng dương (positive): L+ = Li i=1 Chú ý: 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, …} 8
- Biể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át • Vă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ông 9
- Định nghĩa văn phạm Theo 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ạm Dẫ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 , , ...., m 2 * và 1 2, 2 3, ..., m-1 m thì m có thể được dẫn xuất từ 1 1 * m Ngô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) ) 11
- Phân cấp Chomsky trên văn phạm Bằ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 sinh Loạ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)* 12
- Phân cấp Chomsky trên văn phạm Loạ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 → w • Tuyế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 13
- Các ví dụ về văn phạm Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S ) S aS S aA P= A bA A b Đâ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} 14
- Các ví dụ về văn phạm Ví dụ 2: văn phạm G( {S}, {a, b}, P, S ) S aSb P= S ab Đâ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} 15
- Các ví dụ về văn phạm Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S ) S → aSBC S → aBC CB → BC P= aB → ab bB → bb bC → bc cC → cc Đây là văn phạm loại 1 Một dẫn xuất từ S: S aSBC aaBCBC aabCBC aabBCC aabbCC aabbcC aabbcc=a2b2c2 L(G) = {anbncn | n ≥ 1} 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ện INPUT Bộ điều khiển OUTPUT BỘ NHỚ 17
- Phân loại automata Automata đơ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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng VB.net - Chương 2: Ngôn ngữ lập trình Visual Basic. Net
0 p | 253 | 40
-
Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 2: Kiểu dữ liệu
63 p | 126 | 18
-
Bài giảng Lập trình hướng đối tượng - Chương 2: Ngôn ngữ lập trình Java (ĐH Cần Thơ)
160 p | 136 | 17
-
Bài giảng Chuyên đề C#: Chương 2 - Ngôn ngữ lập trình C#
300 p | 92 | 16
-
Bài giảng Chương 2: Tổng quan về ngôn ngữ PHP
54 p | 122 | 14
-
Bài giảng Kiến trúc máy tính - Chương 2: Ngôn ngữ máy - Tập lệnh
68 p | 97 | 11
-
Bài giảng Xử lý ngôn ngữ tự nhiên: Chương 2 - Nguyễn Kiêm Hiếu (ĐH Bách khoa Hà Nội)
8 p | 112 | 11
-
Bài giảng Tin học đại cương - Chương 2: Ngôn ngữ lập trình C
73 p | 49 | 9
-
Bài giảng Chương 2: Nền tảng ngôn ngữ C# - ThS. Phạm Thanh An
32 p | 63 | 7
-
Bài giảng Điều khiển nhúng - Chương 2: Ngôn ngữ VERILOG
43 p | 37 | 7
-
Bài giảng CSDL: Chương 2 - Ngôn ngữ thao tác dữ liệu
22 p | 138 | 5
-
Bài giảng Lập trình ngôn ngữ C - Chương 2: Các khái niệm cơ bản
15 p | 78 | 5
-
Bài giảng Lý thuyết ngôn ngữ lập trình: Chương 2 - CĐ CNTT Hữu nghị Việt Hàn
32 p | 74 | 5
-
Bài giảng Nhập môn Tin học 2 - Chương 7: Ngôn ngữ máy tính
79 p | 27 | 4
-
Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 2 - ThS. Nguyễn Thị Thùy Linh
12 p | 39 | 3
-
Bài giảng Lập trình Java - Chương 2: Ngôn ngữ lập trình Java
41 p | 23 | 2
-
Bài giảng Lập trình môi trường Window - Chương 2: Ngôn ngữ C#
139 p | 18 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn