intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Lý thuyết automata và ngôn ngữ hình thức - Bài 2

Chia sẻ: Le Van Vi | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST
Báo xấu
108
lượt xem 12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Biểu diễn ngôn ngữ một cách tổng quát thông qua văn phạm (grammar) và automata: Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ; Automata: là một máy trừu tượng, hay một 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

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết automata và ngôn ngữ hình thức - Bài 2

  1. Lý thuyết automata và ngôn ngữ hình thức Automata Grammar GIẢNG VIÊN: TS. HÀ CHÍ TRUNG Languague BỘ MÔN: KHMT KHOA CNTT, HVKTQS ĐT:0168.558.21.02 EMAIL: HCT2009@YAHOO.COM ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
  2. Bài 2. Văn phạm và ngôn ngữ hình thức Grammars and formal languagues 2 MỤC ĐÍCH:  Trang bị những khái niệm cơ bản của môn học TA&FL; YÊU CẦU:  Sinh viên nắm vững các khái niệm làm cơ sở cho các bài học tiếp theo. ©copyright by PhD. C.T.Ha, Le Quy Don Technical University
  3. Bài 2. Văn phạm và ngôn ngữ hình thức 3 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automata Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  4. Bài 2. Văn phạm và ngôn ngữ hình thức 4 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automata Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  5. 2.1.1. Các khái niệm cơ bản 5  ĐN 2.1. Tập Σ khác rỗng gồm hữu hạn hay vô hạn các ký hiệu được gọi là bảng chữ cái. Mỗi phần a   tử được gọi là một chữ cái hay một ký hiệu.  ∑ = {a, b, c, … , x, y, z} bảng chữ cái tiếng Anh;  Δ = {α, β, γ, δ, ε, η, ϕ, κ, μ, χ, ν, π, θ, ρ, ζ, η, ω,ξ, ψ};  Г = {0, 1} bảng chữ cái nhị phân;  ĐN 2.2. Cho   a1 , a2 ,..., am  , một dãy   ai1ai 2 ...ait , aij  được gọi là một từ hay một xâu (chuỗi) trên bảng Σ.  ε, 0, 01, 101, 1010, 110011 là các từ trên bảng chữ cái Г = {0,1};  ε, beautiful, happy… là các từ trên Σ = {a, b, c, …, z}. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  6. 2.1.1. Các khái niệm cơ bản 6  ĐN 2.3. Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi • |abca| = 4  ĐN 2.4. Chuỗi rỗng: ký hiệu ε, chuỗi không có ký hiệu nào • |ε| = 0  ĐN 2.5. 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  ĐN 2.6. Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi  ĐN 2.7. 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 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  7. 2.1.1. Các khái niệm cơ bản 7  Ngôn ngữ: theo từ điển, là một hệ thống thích hợp cho việc biểu thị các ý nghĩ, các sự kiện, hay các khái niệm, bao gồm tập các ký hiệu, các qui tắc để vận dụng chúng.  ĐN 2.8: Một ngôn ngữ (hình thức) L trên bộ chữ cái  là một tập hợp các chuỗi từ các ký hiệu của bộ chữ cái .  * : 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 . * = + + {ε} + = * - {ε} Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  8. 2.1.1. Các khái niệm cơ bản 8  Ví dụ 1: Cho  = {0,1} thì:  * = {ε, 0, 1, 00, 01, 10, 11, 000, …}  + = {0, 1, 00, 01, 10, 11, 000, …}  Chuỗi 010210  * vì có số 2   Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  9. 2.1.1. Các khái niệm cơ bản 9  Biểu diễn ngôn ngữ:  Liệt kê các phần tử (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 ngôn ngữ một cách tổng quát thông qua văn phạm (grammar) và automata:  Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ;  Automata: là một máy trừu tượng, hay một 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 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  10. Bài 2. Văn phạm và ngôn ngữ hình thức 10 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automata Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  11. 2.1.2. Các phép toán trên từ 11  ĐN 2.8. Chuỗi nối kết (concatenation): chuỗi được tạo thành bằng cách viết chuỗi thứ nhất, sau đó chuỗi thứ hai, ... o Nối ghép của chuỗi Long và Int là LongInt o 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  ĐN 2.9. Chuỗi đảo ngược (reverse): của chuỗi w, ký hiệu wR, là chuỗi w được viết theo thứ tự ngược lại. o w = abcd → wR = dcba εR = ε  Phép cắt trái của từ α cho từ β - là phần còn lại của từ α sau khi cắt bỏ phần đầu β trong từ α.  Phép cắt phải của từ α cho từ β - là phần còn lại của từ α sau khi cắt bỏ phần đuôi β trong từ α. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  12. Bài 2. Văn phạm và ngôn ngữ hình thức 12 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automata Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  13. 2.1.3. Các phép toán trên ngôn ngữ 13  Vì mỗi ngôn ngữ là một tập hợp nên ta có các phép toán đại số tập hợp như là phép hợp, phép giao, phép hiệu, phép lấy bù trên các ngôn ngữ.  Phép hợp: L1  L2     |   L1 or   L2  *  Phép giao: L1  L2     |   L1 and   L2  *  Phép phần bù (complement): C  L  = * \ L  Phép nhân ghép (concatenation): L1L2 = {w1w2 | w1  L1 và w2  L2} trên bộ chữ cái Σ1  Σ2 o LLL…LL = Li (kết nối i lần trên cùng ngôn ngữ L) o L0 = {ε} Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  14. 2.1.3. Các phép toán trên ngôn ngữ 14  ĐN 2.10. Ngôn ngữ lặp (bao đóng kleene, hoặc *-closure):  L  * Li     L  L2  ...  Ln  ... i 0  ĐN 2.11. Ngôn ngữ lặp cắt (bao đóng dương – positive  closure): L  Li  L  L2  ...  Ln  ... i 1  ĐN 2.12. Ngôn ngữ ngược: LR   * |  R  L  ĐN 2.13. Ngôn ngữ cắt trái của ngôn ngữ X cho ngôn ngữ Y: Z  Y \ X  z * | x  X , y  Y mà x  yz  ĐN 2.14. Ngôn ngữ cắt phải của ngôn ngữ X cho ngôn ngữ Y: Z  X / Y  z  | x  X , y  Y mà x  zy Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  15. Bài 2. Văn phạm và ngôn ngữ hình thức 15 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automata Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  16. 2.2.1. Văn phạm và các khái niệm liên quan 16  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.  Ví dụ đơn giản về văn phạm: → →tôi | anh | chị → →ăn | uống →cơm | phở | sữa | café. Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  17. 2.2.1. Văn phạm và các khái niệm liên quan 17  ĐN 2.15: Văn phạm G là một bộ sắp thứ tự gồm 4 thành phần G = < Σ, Δ, S, P >, trong đó:  Σ - bảng chữ cái, gọi là bảng chữ cái cơ bản (bảng chữ cái kết thúc – terminal symbol);  Δ , Δ ∩ Σ =Ø, gọi là bảng ký hiệu phụ (báng chữ cái không kết thúc – nonterminal symbol);  S ∈ Δ - ký hiệu xuất phát hay tiên đề (start variable);  P - tập các luật sinh (production rules) dạng α→β, α, β ∈ (Σ ∪ Δ)*, trong α chứa ít nhất một ký hiệu không kết thúc (đôi khi, ta gọi chúng là các qui tắc hoặc luật viết lại). Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  18. 2.2.1. Văn phạm và các khái niệm liên quan 18  Qui ước: Trong môn học sử dụng:  Chữ cái in hoa A, B, C,… để biểu thị các biến, trong đó S là ký hiệu xuất phát;  X, Y, Z,… để biểu diễn các ký tự chưa biết hoặc các biến;  a, b, c, d, e,… để biểu diễn chữ cái;  u, v, w, x, y, z,… để biểu diễn chuỗi chữ cái;  α, β, ω,… biểu thị chuỗi các biến hoặc các ký hiệu kết thúc.  Ví dụ 2: G = ({a, b}, {S, A, B}, S, P), trong đó: P: S → aAS|bBS|ε, A → aaA|b, B → aaB|a Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  19. 2.2.1. Văn phạm và các khái niệm liên quan 19  ĐN 2.16. Dẫn xuất trực tiếp: nếu α→β là một luật sinh thì    →    ĐN 2.17. 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 gián tiếp từ 1 1 → * m  ĐN 2.18. Ngôn ngữ L sinh bởi văn phạm G: L (G) = {w  w  Σ* và S → * w}  ĐN 2.19. 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)) Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
  20. 2.2.1. Văn phạm và các khái niệm liên quan 20  Cây dẫn xuất: Giả sử dẫn xuất của từ w= a1a2...an là dãy qui tắc dạng: S  A11A12...A1n  A21A22...A2m...  a1a2...an  Khi đó, ta có thể biểu diễn nó dưới dạng cây như sau: S A11 A12...... A1n ...... A2m A21 A22 A23 a3 a4..... an a1 a2 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2