Bài giảng Lý thuyết tính toán: Bài 02 - Nguyễn Ngọc Tú
lượt xem 4
download
Automat hữu hạn (p01) là nội dung bài 2 thuộc Bài giảng Lý thuyết tính toán. Bài giảng hướng đến trình bày các vấn đề cơ bản về Accepter hữu hạn đơn định; Accepter hữu hạn không đơn định; sự tương đương giữa Accepter hữu hạn đơn định và Accepter hữu hạn không đơn định;...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Lý thuyết tính toán: Bài 02 - Nguyễn Ngọc Tú
- LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA) Bài 02. Automat hữu hạn (p01) Sử dụng slides của các tác giả: Hồ Văn Quân + Nick Hopper GV: Nguyễn Ngọc Tú TIN331 Tu.NguyenNgoc@hoasen.edu.vn
- Nội dung Accepter hữu hạn đơn định Accepter hữu hạn không đơn định Sự tương đương giữa Accepter hữu hạn đơn định và Accepter hữu hạn không đơn định Rút gọn số trạng thái
- Accepter hữu hạn đơn định – DFA Định nghĩa 2.1 Một accepter hữu hạn đơn định (deterministic finite state accepter) hay dfa được định nghĩa bởi bộ năm M = (Q, Σ, δ, q0, F), Q là một tập hữu hạn các trạng thái nội (internal states), Σ là một tập hữu hạn các ký hiệu được gọi là bảng chữ cái ngõ nhập (input alphabet), δ: Q × Σ → Q là HÀM chuyển trạng thái (transition function).
- Accepter hữu hạn đơn định – DFA Để chuyển trạng thái ôtômát dựa vào trạng thái hiện hành q ∈ Q nó đang ở vào và kí hiệu nhập a ∈ Σ nó đang đọc được, nó sẽ chuyển sang trạng thái kế được định nghĩa sẵn trong δ. q0 ∈ Q là trạng thái khởi đầu (initial state), F ⊆ Q là một tập các trạng thái kết thúc (final states) (hay còn được gọi là trạng thái chấp nhận). Chú ý: Ôtômát hữu hạn không có bộ nhớ so với mô hình tổng quát.
- Ví dụ. có hàm chuyển của một ôtômát như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 b a c 1 2
- Hoạt động của DFA Hoạt động của một dfa Tại thời điểm khởi đầu, nó được giả thiết ở trong trạng thái khởi đầu q0, với cơ cấu nhập (đầu đọc) của nó đang ở trên kí hiệu đầu tiên bên trái của chuỗi nhập. Trong suốt mỗi lần di chuyển, cơ cấu nhập tiến về phía phải một kí hiệu, như vậy mỗi lần di chuyển sẽ lấy một kí hiệu ngõ nhập. Khi gặp kí hiệu kết thúc chuỗi, chuỗi là được chấp nhận (accept) nếu ôtômát đang ở vào một trong các trạng thái kết thúc của nó. Ngược lại thì có nghĩa là chuỗi bị từ chối.
- Đồ thị chuyển trạng thái Để biểu diễn một cách trực quan cho dfa người ta sử dụng đồ thị chuyển trạng thái. Cách biểu diễn như sau: Đỉnh biểu diễn các trạng thái. Cạnh biểu diễn các chuyển trạng thái. Nhãn trên các đỉnh là tên các trạng thái. Nhãn trên các cạnh là giá trị hiện tại của kí hiệu nhập. Trạng thái khởi đầu sẽ được nhận biết bằng một mũi tên đi vào không mang nhãn mà không xuất phát từ bất kỳ đỉnh nào Các trạng thái kết thúc được vẽ bằng một vòng tròn đôi.
- Ví dụ 01. Cho dfa sau M = (Q, Σ, δ, q0, F) Q = {q0, q1, q2}, Σ = {0, 1}, F = {q1}, còn δ được cho bởi δ(q0, 0) = q0, δ(q0, 1) = q1, δ(q1, 0) = q0, δ(q1, 1) = q2, δ(q2, 0) = q2, δ(q2, 1) = q1, 0 0 1 1 q0 q1 q2 0 1
- Hàm chuyển trạng thái mở rộng Hàm chuyển trạng thái mở rộng δ* được định nghĩa một cách đệ qui như sau δ*(q, λ) = q, δ*(q, wa) = δ(δ*(q, w), a), ∀ q ∈ Q, w ∈ Σ*, a ∈ Σ. Ví dụ Nếu δ(q0, a) = q1, và δ(q1, b) = q2, Thì δ*(q0, ab) = q2 δ không có định nghĩa cho chuyển trạng thái rỗng, tức là không định nghĩa cho δ(q, λ).
- Ngôn ngữ và DFA Định nghĩa 2.2 Ngôn ngữ được chấp nhận bởi dfa M = (Q, Σ, δ, q0, F) là tập tất cả các chuỗi trên Σ được chấp nhận bởi M. L(M) = {w ∈ Σ*: δ*(q0, w) ∈ F}. Nhận xét: L’(M)= {w ∈ Σ* : δ*(q0, w) ∉ F}.
- Ví dụ 02. Xét dfa M sau a a, b b a, b q0 q1 q2 Dfa trên chấp nhận ngôn ngữ sau L(M) = {anb : n ≥ 0} Trạng thái bẫy (trap state): là trạng thái mà sau khi ôtômát đi vào sẽ không bao giờ thoát ra được. Trạng thái bẫy có thể là trạng thái kết thúc hoặc không. Định nghĩa trên cũng có thể mở rộng ra cho nhóm các trạng thái bẫy kết thúc hay không kết thúc.
- Định lý, bảng truyền Định lý 2.1 Cho M = (Q, Σ, δ, q0, F) là một accepter hữu hạn đơn định, và GM là đồ thị chuyển trạng thái tương ứng của nó. Thì ∀ qi, qj ∈ Q, và w ∈ Σ+, δ*(qi, w) = qj nếu và chỉ nếu có trong GM một con đường mang nhãn là w đi từ qi đến qj. Bảng truyền - (transition table) Là bảng trong đó các nhãn của hàng (ô tô đậm trên hàng trong hình bên) biểu diễn cho trạng thái hiện tại, còn nhãn của cột (ô tô đậm trên cột trong hình bên) biểu diễn cho ký hiệu nhập hiện tại. Các điểm nhập (entry) trong bảng định nghĩa cho trạng thái kế tiếp.
- Định lý, bảng truyền a b a a, b q0 q0 q1 b a, b q1 q2 q2 q0 q1 q2 q2 q2 q2
- Ví dụ 03. Tìm dfa chấp nhận ngôn ngữ Tìm dfa M1 chấp nhận tập tất cả các chuỗi trên Σ = {a, b} được bắt đầu bằng chuỗi ab. Tìm dfa M2 chấp nhận tập tất cả các chuỗi trên Σ = {0, 1}, ngoại trừ những chuỗi chứa chuỗi con 001. a, b 1 0 0, 1 a b 0 0 1 q0 q1 q2 λ 0 00 001 a 1 b q3 a, b
- Ex. Tìm dfa chấp nhận ngôn ngữ L1 = {vwvR ∈ {a, b}*: |v| = 2} L2 = {ababn: n ≥ 0} ∪ {aban: n ≥ 0} L3 = {anbm : (n+m) mod 2= 0} L4 = {w ∈ {a, b}*: na(w) chẵn, nb(w) lẽ} L5 = {w ∈ {0, 1}*: giá trị thập phân của w chia hết cho 5} L6 = {w ∈ {a, b}*: số kí tự a trong chuỗi là một số lẻ}
- Ngôn ngữ chính qui Định nghĩa 2.3 Một ngôn ngữ L được gọi là chính qui nếu và chỉ nếu tồn tại một accepter hữu hạn đơn định M nào đó sao cho L = L(M) b a Ví dụ a a q0 q2 q3 Chứng minh rằng ngôn ngữ b b L= {awa : w ∈ {a,b}*} q1 là chính qui a, b
- Accepter hữu hạn không đơn định Định nghĩa 2.4 Một accepter hữu hạn không đơn định (nondeterministic finite state accepter) hay nfa được định nghĩa bằng bộ năm: M = (Q , Σ, δ, q0, F ) trong đó Q, Σ, q0, F được định nghĩa như đối với accepter hữu hạn đơn định . δ được định nghĩa là: δ : Q × (Σ ∪ { λ}) → 2Q
- Ví dụ 04. q1 a q2 a q3 a 1 0, 1 q0 a q0 0 q1 q2 a q4 q5 a λ (a) (b)
- Hàm chuyển trạng thái mở rộng Định nghĩa 2.5 Cho một nfa, hàm chuyển trạng thái mở rộng được định nghĩa sao cho δ*(qi, w) chứa qj nếu và chỉ nếu có một con đường trong ĐTCTT đi từ qi đến qj mang nhãn w. Điều này đúng với mọi qi, qj ∈ Q và w ∈ Σ*.
- Ví dụ 05. δ*(q1, λ) = {q1, q2, q0} δ*(q2, λ) = {q2, q0} λ δ*(q0, a) = {q1, q2, q0} a b, λ δ*(q1, a) = {q1, q2, q0} q0 q1 q2 δ*(q1, b) = {q2, q0}
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Lý thuyết tính toán Otomat và ngôn ngữ hình thức - GV. Hồ Văn Quân
316 p | 226 | 56
-
Bài giảng Lý thuyết độ phức tạp: Lý thuyết NP - Đầy đủ - PGS. TSKH Vũ Đình Hòa (tt)
41 p | 219 | 51
-
Bài giảng Lý thuyết mật mã và an toàn thông tin: Mật mã cổ điển - Vũ Đình Hòa
48 p | 163 | 22
-
Bài giảng Lý thuyết tính toán: Chương 3 - PGS.TS. Phan Huy Khánh
13 p | 100 | 11
-
Bài giảng Lý thuyết tính toán: Chương 4 - PGS.TS. Phan Huy Khánh
10 p | 116 | 11
-
Bài giảng Lý thuyết tính toán: Chương 1 - PGS.TS. Phan Huy Khánh
10 p | 152 | 8
-
Bài giảng Lý thuyết đồ thị: Chương 10 - PGS.TS. Hoàng Chí Thành
25 p | 10 | 6
-
Bài giảng Lý thuyết ngôn ngữ lập trình: Chương 6 - CĐ CNTT Hữu nghị Việt Hàn
13 p | 91 | 6
-
Bài giảng Lý thuyết tính toán: Bài 03 - Nguyễn Ngọc Tú
53 p | 87 | 5
-
Bài giảng Lý thuyết tính toán: Bài 04 - Nguyễn Ngọc Tú
32 p | 90 | 5
-
Bài giảng Lý thuyết mật mã: Chương 1 - PGS.TS Đỗ Trọng Tuấn
57 p | 36 | 5
-
Bài giảng Lý thuyết mạng máy tính: Chương 7 - ThS. Nguyễn Đức Thiện
13 p | 11 | 4
-
Bài giảng Lý thuyết tính toán: Bài 00 - Nguyễn Ngọc Tú
7 p | 81 | 3
-
Bài giảng Lý thuyết nhận dạng – Chương 4: Phân lớp dựa trên tối ưu hóa hàm lượng giá
47 p | 53 | 3
-
Bài giảng Lý thuyết tính toán: Bài 06 - Nguyễn Ngọc Tú
23 p | 84 | 3
-
Bài giảng Lý thuyết tính toán: Bài 05 - Nguyễn Ngọc Tú
28 p | 90 | 3
-
Bài giảng Lý thuyết tính toán: Bài 01 - Nguyễn Ngọc Tú
29 p | 91 | 3
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