Bài giảng Toán giải tích - Chương 3: Automata hữu hạn và biểu thức chính quy
lượt xem 6
download
Bài giảng "Toán giải tích - Chương 3: Automata hữu hạn và biểu thức chính quy" cung cấp cho người đọc các kiến thức: Khái niệm DFA & NFA, sự tương đương giữa DFA & NFA, biểu thức chính quy, các tính chất của tập chính quy. Mời các bạn cùng tham khảo nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Toán giải tích - Chương 3: Automata hữu hạn và biểu thức chính quy
- Chương 3: Automata hữu hạn & Biểu thức chính quy Nội dung: • Khái niệm DFA & NFA • Sự tương đương giữa DFA & NFA • Biểu thức chính quy • Các tính chất của tập chính quy 1
- Đị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Ớ 2
- 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ị) 3
- Phân loại FA DFA Deterministic Finite Automata FA (Finite Automata) NFA Nondeterministic Finite Automata Biểu thức chính quy 4
- Automata hữu hạn đơn định (DFA) Ví dụ: c 1 Input 0 1 1 0 0 1 0 1 Start q0 1 q1 0 0 Bộ điều khiển a b Trạng thái bắt đầu 0 0 1 q2 q3 Trạng thái kết thúc 1 d x Phép chuyển trên nhãn x Q : tập hữu hạn các trạng thái (p, q…) Σ : bộ chữ cái nhập (a, b … ; w, x, y …) M=(Q, Σ, δ, q0, F) δ : hàm chuyển, ánh xạ: Q x Σ → Q q0 Q : trạng thái bắt đầu. F Q : tập các trạng thái kết thúc. 5
- Mở rộng hàm chuyển trạng thái 1. δ(q, ) = q 2. δ(q, wa) = δ( δ(q,w), a) với w, a Ngôn ngữ được chấp nhận: L(M) = { x | δ( q0, x ) F } Ngôn ngữ Ví dụ: chuỗi nhập w=110101 chính quy • δ(q0, 1) = q1 • δ(q0, 11) = δ(q1, 1) = q0 • δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2 • δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3 • δ(q0, 11010) = … = δ(q3, 0) = q1 • δ(q0, 110101) = … = δ(q1, 1) = q0 F 6
- Giải thuật hình thức • Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ L(M) được chấp nhận bởi automata M. • Input: chuỗi nhập x$ • Output: câu trả lời ‘YES’ hoặc ‘NO’ • Giải thuật: q := q0 ; c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} While c $ do begin q := δ(q, c); c := nextchar ; end If (q in F) then write("YES") else write("NO"); 7
- Automata hữu hạn không đơn định (NFA) • Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001 1 1 0 0 Start 0 0 q0 q3 q4 1 q1 q0 0 q0 1 q0 0 q0 0 q0 1 q0 1 0 1 0 0 1 q3 q1 q3 q3 q1 q2 0 0 1 1 q4 q4 Nhận xét: • Ứ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. 8 • DFA là một trường hợp đặc biệt của NFA
- Định nghĩa NFA Q : tập hữu hạn các trạng thái. Σ : bộ chữ cái nhập. M=(Q, Σ, δ, q0, F) δ : hàm chuyển ánh xạ Q x Σ → 2Q q0 Q : trạng thái bắt đầu. F Q : tập các trạng thái kết thúc. Chú ý: khái niệm δ(q, a) là tập hợp tất cả các trạng thái p sao cho có phép chuyển từ trạng thái q trên nhãn a. Hàm chuyển trạng thái mở rộng: • δ(q, ) = {q} • δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà pδ(r, a) } = δ( δ(q,w), a) • δ(P, w) = qP δ(q, w) với P Q 9
- Ví dụ về NFA Ví dụ: xét chuỗi nhập w=01001 và NFA đã cho ở trên • M( {q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q2, q4} ) δ Input • δ(q0, 0) = {q0,q3} Trạng thái 0 1 • δ(q0, 01) = δ( δ(q0, 0), 1) q0 {q0,q3} {q0,q1} = δ({q0, q3},1) = δ(q0, 1) q1 Ø {q2} δ(q3, 1) = {q0, q1} q2 {q2} {q2} • δ(q0, 010) = {q0, q3} q3 {q4} Ø • δ(q0, 0100) = {q0, q3, q4} q4 {q4} {q4} • δ(q0, 01001) = {q0, q1, q4} Do q4 F nên w=01001 L(M) 10
- Sự tương đương giữa DFA & NFA Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA chấp nhận L. Giả sử NFA M={Q, Σ, δ, q0, F} chấp nhận L Ta xây dựng DFA M’={Q’, Σ, δ’, q0’, F’} chấp nhận L • Q’ = 2Q . Một phần tử trong Q’ được ký hiệu là [q0, q1, …, qi] với q0, q1, …, qi Q • q0’ = [q0] • F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc trong tập F của M • Hàm chuyển δ’([q1, q2,..., qi], a) = [p1, p2,..., pj] nếu và chỉ nếu δ({q1, q2,..., qi }, a) = {p1, p2,..., pj} 11
- Ví dụ về sự tương đương giữa DFA & NFA Ví dụ: NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) với hàm chuyển δ(q0,0) = {q0, q1}, δ(q0,1) = {q1}, δ(q1,0) = , δ(q1,1) = {q0, q1} Ta sẽ xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q0], F’) • Q’ = {, [q0], [q1], [q0, q1]} • F’ = {[q1], [q0, q1]} • Hàm chuyển δ’ δ’(, 0) = δ’(, 1) = δ’([q0], 0) = [q0, q1] δ’([q0], 1) = [q1] δ’([q1], 0) = δ’([q1], 1) = [q0, q1] δ’([q0, q1], 0) = [q0, q1] δ’([q0, q1], 1) = [q0, q1] 12
- NFA với - dịch chuyển (NFA) Ví dụ: xây dựng NFA chấp nhận chuỗi 0*1*2* 0 1 2 Start 0, 1 1, 2 q0 q1 q2 0, 1, 2 0 1 2 Start q0 q1 q2 Định nghĩa: NFA M(Q, Σ, δ, q0, F) • δ : hàm chuyển ánh xạ Q x (Σ {}) → 2Q • Khái niệm δ(q, a) là tập hợp các trạng thái p sao cho có phép chuyển nhãn a từ q tới p, với a (Σ {}) 13
- Mở rộng hàm chuyển trạng thái cho NFA Định nghĩa -CLOSURE: ● -CLOSURE(q) = { p | có đường đi từ q tới p theo nhãn } ● -CLOSURE(P) = qP -CLOSURE(q) Hàm chuyển trạng thái mở rộng: mở rộng δ thành δ* • δ* : Q x Σ* → 2Q • δ*(q, w) = { p | có đường đi từ q tới p theo nhãn w, trên đường đi có thể chứa cạnh nhãn } Ta có: • δ*(q, ) = -CLOSURE(q) • δ*(q,a) = -CLOSURE(δ(δ*(q, ),a)) • δ*(q, wa) = -CLOSURE( δ( δ*(q, w), a) ) Cách khác: δ*(q, wa) = -CLOSURE(P) với P = { p | r δ*(q, w) và p δ(r, a) } • δ*(R, w) = qR δ*(q, w) 14
- Mở rộng hàm chuyển trạng thái cho NFA 0 1 2 Ví dụ: Start q0 q1 q2 Xét chuỗi nhập w = 012 • δ*(q0, ) = -CLOSURE(q0) = {q0, q1, q2} • δ*(q0, 0) = -CLOSURE(δ(δ*(q0, ), 0)) = -CLOSURE(δ({q0, q1, q2}, 0)) = -CLOSURE(δ(q0, 0) δ(q1, 0) δ(q2, 0) ) = -CLOSURE( {q0} ) = -CLOSURE({q0}) = {q0, q1, q2} • δ*(q0, 01) = -CLOSURE(δ(δ*(q0, 0), 1)) = -CLOSURE(δ({q0, q1, q2}, 1)) = -CLOSURE({q1}) = {q1,q2} • δ*(q0, 012) = -CLOSURE(δ(δ*(q0, 01), 2)) = -CLOSURE(δ({q1, q2}, 2)) = -CLOSURE({q2}) = {q2} • Do q2 F nên w L(M) 15
- Giải thuật hình thức cho NFA Mục đích: mô phỏng hoạt động của NFA Input: chuỗi nhập x$ Output: câu trả lời ‘YES’ (x được chấp nhận) hoặc ‘NO’ Giải thuật: q := -CLOSURE (q0) ; c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo} While c $ do begin q := -CLOSURE (δ(q, c)); c := nextchar ; end If (q in F) then write("YES") else write("NO"); 16
- Sự tương đương giữa NFA và NFA Định lý 2: nếu L được chấp nhận bởi một NFA có -dịch chuyển thì L cũng được chấp nhận bởi một NFA không có -dịch chuyển. Giả sử: NFA M(Q, Σ, δ, q0, F) chấp nhận L Ta xây dựng: NFA M’={Q, Σ, δ’, q0, F’} Với: • F’ = F q0 nếu -CLOSURE(q0) chứa một trạng thái thuộc F. Ngược lại, F’ = F • δ’(q, a) = δ*(q, a) 17
- Sự tương đương giữa NFA và NFA 0 1 2 Ví dụ: Start q0 q1 q2 Xây dựng NFA tương đương M’={Q, Σ, δ’, q0, F’} • Q = {q0, q1, q2} • Σ = {0, 1, 2} • Trạng thái bắt đầu: q0 • F’ = {q0, q2} δ’ Inputs • Hàm chuyển δ’ Trạng thái 0 1 2 0 1 2 q0 {q0, q1, q2} {q1, q2} {q2} Start 0, 1 1, 2 q0 q1 q2 q1 {q1, q2} {q2} q2 {q2} 0, 1, 2 18
- Xây dựng DFA từ NFA() Ví dụ: xây dựng DFA tương đương với NFA sau: M = (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10}) a 2 3 a b b Start 0 1 6 7 8 9 10 b 4 5 Ta xây dựng DFA M’= (Q’, Σ, δ’, q0’, F’) tương đương M • Trạng thái bắt đầu: q0’ ↔ -CLOSURE(q0) • F’ = { p | trong ký hiệu của p có chứa ít nhất một trạng thái của F } • Xây dựng hàm chuyển δ’ 19
- Giải thuật xây dựng hàm chuyển δ’ Giải thuật: T := -CLOSURE (q0) ; T chưa được đánh dấu ; Thêm T vào tập các trạng thái Q’ của DFA ; While Có một trạng thái T của DFA chưa được đánh dấu do Begin Đánh dấu T; { xét trạng thái T} For Với mỗi ký hiệu nhập a do begin U:= -closure((T, a)) If U không có trong tập trạng thái Q’ của DFA then begin Thêm U vào tập các trạng thái Q’ của DFA ; Trạng thái U chưa được đánh dấu; [T, a] := U;{[T, a] là phần tử của bảng chuyển DFA} end; end; End; 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng môn giải tích A3: Tích phân bội, tích phân đường, tích phân mặt
79 p | 999 | 274
-
Bài giảng Toán giải tích 1: Chương 1 - Dương Minh Đức
61 p | 184 | 23
-
Bài giảng Toán giải tích 1: Chương 8 - Dương Minh Đức
57 p | 86 | 10
-
Bài giảng Toán giải tích 1: Chương 7 - Dương Minh Đức
88 p | 100 | 10
-
Bài giảng Toán giải tích 1: Chương 6 - Dương Minh Đức
64 p | 112 | 10
-
Bài giảng Toán giải tích 1: Chương 3 - Dương Minh Đức
30 p | 97 | 10
-
Bài giảng Toán giải tích 1: Chương 5 - Dương Minh Đức
90 p | 94 | 9
-
Bài giảng Toán giải tích 1: Chương 4 - Dương Minh Đức
29 p | 99 | 9
-
Bài giảng Toán giải tích 1: Chương 2 - Dương Minh Đức
49 p | 97 | 9
-
Bài giảng Toán giải tích - Chương 5: Văn phạm phi ngữ cảnh
27 p | 153 | 9
-
Bài giảng Toán giải tích - Chương 7: Máy Turing
12 p | 178 | 8
-
Bài giảng Toán giải tích: Phần 1 - Trường CĐ Cộng đồng Đồng Tháp
52 p | 30 | 5
-
Bài giảng Toán giải tích: Phần 2 - Trường CĐ Cộng đồng Đồng Tháp
63 p | 29 | 5
-
Bài giảng Toán giải tích - Chương 2: Ngôn ngữ và sự phân cấp Chomsky
18 p | 72 | 3
-
Bài giảng Toán giải tích - Chương 6: Automata đẩy xuống
16 p | 59 | 2
-
Bài giảng Toán giải tích - Chương 1: Bổ túc toán
20 p | 71 | 2
-
Bài giảng Toán giải tích - Chương 4: Văn phạm chính quy và các tính chất
9 p | 97 | 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