Bài giảng Automat Hữu hạn

Automat Hữu HạnFinite 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. * Introductory Example An automaton that accepts all legal Pascal identifiers: 1 2 3 Letter Digit Letter or Digit Letter or Digit "yes" "no" * 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 * Operational Manner Tại thời điểm ban đầu, nó được giả định đang ở trong trạng thái 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 phải một ký hiệu. 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 những trạng thái kết thúc của nó. Ngược lại thì chuỗi bị từ chối. * 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 * 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 Dfa này chấp nhận chuỗi 001, 011, 010???. * 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) 	 * Languages and DFAs Ngôn ngữ được chấp nhận bởi một dfa M; M = (Q, , , q0, F) là một tập hợp tất cả các chuỗi trên  chấp nhận bởi M: L(M) = {w* | *(q0, w)F} L(M) = {w* | *(q0, w)F} 	 * Example 1 M = ({q0, q1, q2}, {a, b}, , q0, {q1}) L(M) = ? 	 q0 q1 q2 a, b a, b a b * Example 1 M = ({q0, q1, q2}, {a, b}, , q0, {q1}) L(M) = {anb | n  0} 	 q0 q1 q2 a, b a, b a b trap state Không thoát được * Theorem Cho M = (Q, , , q0, F) là 1 accepter hữu hạn đơn định và GM là đồ thị chuyển trạng thái tương ứng của nó. Khi đó với mọi qi, qj  Q và w+ thì *(qi, w) = qj iff trong GM có một đường mang nhãn w đi từ qi đến qj 	 * 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} 	 * Example 2 L(M) = {w{a, b}* | w starts with ab} 	 * 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} 	 * Example 3 L(M) = {w{0, 1}* | w does not contain 001} 	  0 001 0 0, 1 1 1 00 0 1 0 trap state * Regular Languages L is regular iff L = L(M) for some DFA M 	 * Example 4 Hãy chỉ ra rằng ngôn ngữ L = {awa | w{a, b}*} là chính quy 	 * Example 4 L = {awa | w{a, b}*} 	 * Example 5 Chỉ ra rằng L2 là chính quy. L = {awa | w{a, b}*} L2 = {aw1aaw2a | w1, w2{a, b}*} 	 * Example 5 L2 = {aw1aaw2a | w1, w2{a, b}*} 	 * Nondeterministic Finite Automata (NFA) M = (Q, , , q0, F) 	Q: finite set of internal states 	: finite set of symbols - input alphabet 	: Q  (  {})  2Q	transition function 	q0Q: initial state 	FQ: set of final states * Example 6 * Example 7 Automat chấp nhận chuỗi , 10, 1010, và 101010, nhưng không chấp nhận chuỗi 110, và 10100. * Extended Transition Function *(qi, w) = Qj Qj là tập tất cả những trạng có thể của automat, khi automat ở trạng thái qi và đọc w. * Extended Transition Function *(qi, w) contains qj iff there is a walk labelled w from qi to qj * Example 8 *(q1, a) = ? *(q2, ) = ? 	 q0 q1 q2  a  * Example 8 *(q1, a) = {q0, q1, q2} *(q2, ) = {q0, q2} 	 q0 q1 q2  a  * Example 8 *(qi, w) = ? Evaluate all walks of length at most  + (1 + )|w|  is the number of -edges 	 q0 q1 q2  a  * Languages and NFAs Ngôn ngữ L được chấp nhận bởi một nfa M = (Q, , , q0, F) được định nghĩa như là một tập tất cả các chuỗi được chấp nhận bởi M L(M) = {w* | *(q0, w)  F  } 	 * Languages and NFAs q0 q1 q2 1 0 0, 1  L(M) = ? * Languages and NFAs q0 q1 q2 1 0 0, 1  L(M) = {(10)n | n  0} * Languages and NFAs *(q0, 110) = (q2, 0) =  	 dead configuration Điều gì xảy ra khi automat này thực hiện với chuỗi w = 110? * Homework Exercises: 1, 5, 6, 11, 14, 17, 15, 17 of Section 2.1 - Linz’s book. Exercises: 3, 4, 6, 7, 9, 10 of Section 2.2 - Linz’s book. Reading: Why nondeterminism - Linz’s book. Presentation: Section 2.4 - Linz’s book (procedures mark and reduce). 	 * Equivalence of DFAs and NFAs A class of automata may be more powerful than another. DFA is a restricted kind of NFA. 	DFA: (qi, a) = qj 	NFA: (qi, a) = {qj} =>Bất cứ ngôn ngữ nào được chấp nhận bởi một dfa thì cũng được chấp nhận bởi nfa. Nhưng điều ngược lại thì không hiển nhiên. * Equivalence of DFAs and NFAs DFA and NFA are equally powerful. 	NFA: *(q, w) = {qi, qj, ..., qk} 	 a label of one state * Example 9 	 q0 q1 q2  a b a Biến đổi nfa trong sang một dfa tương đương * Example 9 ({q0}, a) = {q1, q2} ({q0}, b) =  	 q0 q1 q2  a b a * Example 9 ({q0}, a) = {q1, q2} ({q0}, b) =  ({q1, q2}, a) = {q1, q2} ({q1, q2}, b) = {q0} 	 q0 q1 q2  a b a * Example 9 {q0} {q1,q2} b a  b a a, b * Theorem Given MN = (QN, , N, q0N, FN) there exists MD = (QD, , D, q0D, FD) such that L(MD) = L(MN) 	 * Procedure NFADFA Create GD with vertex q0D = {q0N}. Repeat: Take any vertex {qi, qj, ..., qk} of GD that has a missing edge for a. Compute *(qi, a), *(qj, a), ..., *(qk, a). Create new vertex {ql, qm, ..., qn} = *(qi, a)*(qj, a) ... *(qk, a) if not exist. Add edge from {qi, qj, ..., qk} to {ql, qm, ..., qn} with label a. Every state of GD containing qf  FN is a final vertex. If   L(MN) then {q0N} is also a final vertex. * Example 10 	 q0 q1 q2 0, 1 0 0, 1 1 Theorem Một kết luận quan trọng mà chúng ta rút ra được từ định lý đó là mỗi ngôn ngữ được chấp nhận bởi một nfa là chính qui. * Homework Exercises: 3, 8, 11, 12 of Section 2.3 - Linz’s book. Exercises: 1, 4 of Section 2.4 - Linz’s book. Programming: Implement DFAs