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 3

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

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

Automata là một máy trừu tượng (mô hình tính toán) có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ. Finite automata (FA) - mô hình tính toán hữu hạn: có khởi đầu và kết thúc, mọi thành phần đều có kích thước hữu hạn cố định và không thể mở rộng trong suốt quá trình tính toán;

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 3

  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 © PhD. C.T.Ha, Le Quy Don Technical University
  2. Bài 3. Ngôn ngữ và automata hữu hạn (Formal Languagues and Finite Automata) 2 MỤC ĐÍCH:  Trang bị những khái niệm về automata hữu hạn (FA);  Phân loại FA;  các phép biến đổi tương đương giữa các loại FA;  Biểu thức chính qui (RE) và sự tương đương với FA; YÊU CẦU:  Sinh viên nắm vững các khái niệm, các thuật toán biến đổi và làm các dạng bài tập. © PhD. C.T.Ha, Le Quy Don Technical University
  3. Bài 3. Ngôn ngữ và automata hữu hạn 3 3.1. Các khái niệm sơ lược 3.2. Automata hữu hạn đơn định (DFA) 3.3. Automata hữu hạn đa định (NFA) 3.4. Automata với dịch chuyển ε (NFAε) 3.5. Sự tương đương giữa DFA và NFA 3.6. Sự tương đương giữa NFAε và DFA 3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  4. Bài 3. Ngôn ngữ và automata hữu hạn 4 3.1. Các khái niệm sơ lược 3.2. Automata hữu hạn đơn định (DFA) 3.3. Automata hữu hạn đa định (NFA) 3.4. Automata với dịch chuyển ε (NFAε) 3.5. Sự tương đương giữa DFA và NFA 3.6. Sự tương đương giữa NFAε và DFA 3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  5. 3.1. Các khái niệm sơ lược 5  Automata là một máy trừu tượng (mô hình tính toán) có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ.  Finite automata (FA) - mô hình tính toán hữu hạn: có khởi đầu và kết thúc, mọi thành phần đều có kích thước hữu hạn cố định và không thể mở rộng trong suốt quá trình tính toán;  Hoạt động theo theo từng bước rời rạc (steps);  Nói chung, thông tin ra sản sinh bởi một FA phụ thuộc vào cả thông tin vào hiện tại và trước đó. Nếu sử dụng bộ nhớ (memory), giả sử rằng nó có ít nhất một bộ nhớ vô hạn;  Sự phân biệt giữa các loại automata khác nhau chủ yếu dựa trên việc thông tin có thể được đưa vào memory hay không; Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  6. 3.1. Các khái niệm sơ lược 6 DFA (Deterministic RE (Regular Finite Automata) Expression) FA (Finite Automata) NFA RG (Regular (Nondeterministic Grammar) or RL Finite Automata) Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  7. 3.1. Các khái niệm sơ lược 7  Đoán nhận ngôn ngữ: đoán nhận các từ của ngôn ngữ đó.  Hoạt động của automata bắt đầu từ một trạng thái đặc biệt, trang thái đầu tiên (start state);  Giả sử rằng tại mỗi thời điểm (step, time step), automata đang ở một trạng thái nào đó (current state), đầu vào của automata đón nhận một ký tự của chuỗi cần xử lý, dưới tác động của ký tự đó automata chuyển sang một trạng thái kế tiếp (next state);  Chuỗi được đoán nhận nếu trạng thái cuối cùng của automata rơi vào một trong các trạng thái kết thúc (finish states). Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  8. Bài 3. Ngôn ngữ và automata hữu hạn 8 3.1. Các khái niệm sơ lược 3.2. Automata hữu hạn đơn định (DFA) 3.3. Automata hữu hạn đa định (NFA) 3.4. Automata với dịch chuyển ε (NFAε) 3.5. Sự tương đương giữa DFA và NFA 3.6. Sự tương đương giữa NFAε và DFA 3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  9. 3.2. Automata hữu hạn đơn định (DFA) 9  Định nghĩa 3.1: một DFA là một bộ năm: A=(Q, Σ, δ, q0, F), trong đó: Q : tập khác rỗng, tập hữu hạn các trạng thái (p, q…); Σ : bộ chữ cái nhập vào (a, b, c …); δ : D→ Q, hàm chuyển (hay ánh xạ), D ⊆ Q × Σ, có nghĩa là δ(p, a) =q hoặc δ(p, a) = Ø, trong đó p, q  Q , a  Σ; q0  Q : trạng thái bắt đầu (start state); F  Q : tập các trạng thái kết thúc (finish states). Trong trường hợp D = Q × Σ ta nói A là một DFA đầy đủ. Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  10. 3.2. Automata hữu hạn đơn định (DFA) 10  Biểu diễn automata: Cho một automata thực chất là cho hàm chuyển trạng thái của nó, có thể cho dưới dạng bảng chuyển trạng thái hoặc cho dưới dạng đồ thị chuyển.  Định nghĩa 3.2: Đồ thị chuyển là một đa đồ thị có hướng (có thể có khuyên) G: Tập đỉnh của G được gán nhãn bởi các phần tử thuộc Q, các cung được gán nhãn bởi các phần tử thuộc Σ, nếu a ∈ Σ, p,q ∈ Q và δ(q, a) = p thì sẽ có một cung từ đỉnh q tới đỉnh p được gán nhãn a. Đỉnh vào của đồ thị chuyển ứng với trạng thái ban đầu q0.  Định nghĩa 3.3: Bảng chuyển – bảng có kích cỡ |Q|×|Σ|, trong đó dòng i cột j của bảng là 𝛿(𝑞𝑖 , 𝑎𝑗 ) hoặc bỏ trống. Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  11. 3.2. Automata hữu hạn đơn định (DFA) 11 A  Q, ,  , q0 , F  Trạng thái bắt đầu Q  q0 , q1 ,..., qm  Trạng thái kết thúc   a1 , a2 ,..., an  x Phép chuyển trên nhãn x Bảng chuyển Đồ thị chuyển 1 q0 q1 1 0 0 0 0 1 q2 q3 1 Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  12. 3.2. Automata hữu hạn đơn định (DFA) 12 0 11 0,1 1 1 0111 111 1 0 0 1 Thứ tự đọc từ trái qua phải Automata đoán nhận chuỗi khi đọc hết xâu và rơi vào trạng thái kết thúc Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  13. 3.2. Automata hữu hạn đơn định (DFA) 13  Ví dụ 3.1: Cho automata A = ({q0; q1; q2}; {0, 1}, , q0, {q1}) với hàm chuyển được cho dưới dạng bảng chuyển và đồ thị chuyển như sau: Ngôn ngữ được đoán nhận bởi automat A: L = {1*0*01x : x  {0, 1}*} Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  14. 3.2. Automata hữu hạn đơn định (DFA) 14  Ví dụ 3.2: Automat sau nhận dạng ngôn ngữ gồm chẵn các số 1 và chẵn các số 0.  Quá trình đoán nhận các xâu: 001011, 101010, 10010 Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  15. 3.2. Automata hữu hạn đơn định (DFA) 15  Định nghĩa 3.4: Mở rộng của một ánh xạ δ là δ’ biến đổi (trạng thái, chuỗi) sang trạng thái. Có nghĩa là: 1. δ’(q, ) = q; 2. δ’(q, wa) = δ’(δ’(q,w), a) với  w, a.  Chuỗi ω = a1a2...an được đoán nhận bởi DFA A (có nghĩa là  '  q0 ,    F ) nếu tồn tại một đường đi bắt đầu từ trạng thái đầu q0 và kết thúc ở trạng thái kết với dãy nhãn của đường đi là a1a2...an.  Ngôn ngữ được chấp nhận bởi một automata A: L(A) = { x | δ’( q0, x )  F }  Các ngôn ngữ chấp nhận bởi automata hữu hạn đơn định được gọi là ngôn ngữ chính quy. Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  16. 3.2. Automata hữu hạn đơn định (DFA) 16  Thuật toán đoán nhận chuỗi: q:= q0; c:= ký hiệu tiếp theo của chuỗi; while (C < > ε) do { q:= δ(q, c); c:= ký hiệu tiếp theo của chuỗi; }; if (q in F) return (true); else return (false); Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  17. Bài 3. Ngôn ngữ và automata hữu hạn 17 3.1. Các khái niệm sơ lược 3.2. Automata hữu hạn đơn định (DFA) 3.3. Automata hữu hạn đa định (NFA) 3.4. Automata với dịch chuyển ε (NFAε) 3.5. Sự tương đương giữa DFA và NFA 3.6. Sự tương đương giữa NFAε và DFA 3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE 3.7.4. Sự tương đương giữa NFAε và RE Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  18. 3.3. Automata hữu hạn đa định (NFA) 18  DFA tại một thời điểm với một trạng thái và một ký tự nhập vào thì máy chỉ có thể chuyển đến không nhiều hơn một trạng thái.  NFA là automata mà ứng với một trạng thái và một ký tự nhập, có thể có không, một hoặc nhiều phép chuyển trạng thái.  Ví dụ 3.3: automata đa định sau nhận dạng các xâu kết thúc bằng 01 Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  19. 3.3. Automata hữu hạn đa định (NFA) 19  Xét quá trình automata A nhận dạng xâu 00101: Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012
  20. 3.3. Automata hữu hạn đa định (NFA) 20  Định nghĩa 3.5: Automat hữu hạn đa định được định nghĩa bởi bộ 5: A = (Q, , , q0, F) trong đó: Q - tập hữu hạn các trạng thái.  - là tập hữu hạn các chữ cái.  - là ánh xạ chuyển trạng thái. : Q   2Q q0  Q là trạng thái khởi đầu. F  Q là tập trạng thái kết;  Ánh xạ δ là một hàm đa trị (hàm không đơn định), vì vậy A được gọi là không đơn định; Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/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