Chương 2 -Automat Hữu Hạn

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:47

Thêm vào BST

Báo xấu

181
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Introductory Example Chúng ta hãy tạo ra một ngôn ngữ nhỏ gấn như ngôn ngữ Pascal Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. , ||l a|b|… 0|1… , , , và là các biến a, b, …, 0, 1, … là những ký tự kết thúc

Chủ đề:

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

Lưu

Nội dung Text: Chương 2 -Automat Hữu Hạn

Automat Hữu Hạn Finite Automata Dr. Huỳnh Trung Hiếu Faculty of Information Technology HoChiMinh City University of Industry
Introductory Example Chúng ta hãy tạo ra một ngôn ngữ nhỏ gần như ngôn ngữ Pascal.  Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. ,  ||λ  a|b|…  0|1…  , , , và là các biến a, b, …, 0, 1, … là những ký tự kết thúc
Introductory Example Một dẫn xuất cho định danh x1  => => x => x => x1 => x1
Biểu diễn Automat Dùng đồ thị:  Các nút là các trạng thái nội.  Các cạnh là các chuyển dịch.  Nhãn của các cạnh cho biết điều gì xảy ra.  a 1 2
Introductory Example An automaton that accepts all legal Pascal identifiers: Letter "yes" 1 2 Digit Letter or Digit "no" 3 Letter or Digit 5
Deterministic Finite Automata (DFA) Một accepter hữu hạn đơn định hay một DFA được định nghĩa bởi bộ năm: M = (Q, ∑, δ , q0, F) Q: finite set of internal states ∑: finite set of symbols input alphabet δ : Q × ∑ → Q transition function q0∈Q: initial state F⊆ Q: set of final states 6
Operational Manner Tại thời điểm ban đầu, nó được giả định đang ở trong trạng thái Input file bắt đầu q0, với cơ chế nhập đang ở tại ký hiệu bên trái nhất của chuỗi nhập vào. Trong mỗi lần di chuyển của automat, đầu đọc tiến về phía Control unit phải một ký hiệu. q0 Khi gặp ký hiệu kết thúc chuỗi, chuỗi nhập được chấp nhận nếu như automat đang ở một trong yes/no những trạng thái kết thúc của nó. Ngược lại thì chuỗi bị từ chối. 7
Transition Graphs M = (Q, ∑, δ , q0, F) |Q| vertices (circles)  Edge (qi, qj) labelled a for δ (qi, a) = qj  Initial verticle q0  Final vertices (double circles) in F  8
Example 1 M = ({q0, q1, q2}, {0, 1}, δ , q0, {q1}) δ (q0, 0) = q0 δ (q0, 1) = q1 δ (q1, 0) = q0 δ (q1, 1) = q2 δ (q2, 0) = q2 δ (q2, 1) = q1 1 0 0 0 q0 q1 q2 1 1 Dfa này chấp nhận chuỗi 001, 011, 010???. 9
Extended Transition Function δ *: Q × ∑* → Q extended transition function Nếu δ (q0, a) = q1 và δ (q1, b) = q2 thì δ *(q0, ab) = q2 Một cách hình thức, chúng ta định nghĩa δ * đệ quy như sau: δ *(q, λ ) = q δ *(q, wa) = δ (δ *(q, w), a) 10
Languages and DFAs Ngôn ngữ được chấp nhận bởi một dfa M; 11
Example 1 M = ({q0, q1, q2}, {a, b}, δ , q0, {q1}) a a, b b a, b q0 q1 q2 L(M) = ? 12
Example 1 M = ({q0, q1, q2}, {a, b}, δ , q0, {q1}) a a, b b a, b q0 q1 q2 trap state Không thoát được L(M) = {a b | n ≥ 0} n 13
Theorem 14
Example 2 Tìm một accepter hữu hạn nhận ra tập hợp tất  cả các chuỗi trên ∑= {a, b} bắt đầu với chuỗi ab. L(M) = {w∈{a, b}* | w starts with ab} 15
Example 2 L(M) = {w∈{a, b}* | w starts with ab} a, b b a q0 q1 q2 a b trap state q3 a, b 16
Example 3 Tìm một dfa chấp nhận tất cả các chuỗi trên {0, 1}, ngoại trừ những chuỗi chứa chuỗi con 001. L(M) = {w∈{0, 1}* | w does not contain 001} 17
Example 3 L(M) = {w∈{0, 1}* | w does not contain 001} 0, 1 1 0 1 0 1 λ 0 00 001 trap state 0 18
Regular Languages L is regular iff L = L(M) for some DFA M 19
Example 4 Hãy chỉ ra rằng ngôn ngữ L = {awa | w∈{a, b}*} là chính quy 20