tailieunhanh - Chapter 2: Finite Automata

Chương 2 của bộ Slide tiếng Anh môn học lý thuyết automata và ngôn ngữ hình thức đầy đủ của trường ĐHBK . Bộ Slide này có tổng cộng 7 chương. | Chapter 2: Finite Automata Objectives Mastering the following concepts: Deterministic Finite Accepter (DFA) Nondeterministic Finite Accepter (NFA) DFA and NFA Equivalence Deterministic Finite Accepter (DFA) 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 Mechanism Control unit q0 Input file yes/no Question: What is the difference between a general automaton and a DFA? Transition Graph M = (Q, , , q0, F) |Q| vertices (circles) Edge (qi, qj) labelled a for (qi, a) = qj Initial vertice q0 Final vertices (double circles) in F Example 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 q0 q1 1 q2 1 0 0 0 1 Example 1 2 3 Letter Digit Letter or Digit Letter or Digit 2 Extended Transition Function *(q, ) = q *(q, wa) = ( *(q, w), a) Example : (q0, a) = q1 & (q1, b) = | Chapter 2: Finite Automata Objectives Mastering the following concepts: Deterministic Finite Accepter (DFA) Nondeterministic Finite Accepter (NFA) DFA and NFA Equivalence Deterministic Finite Accepter (DFA) 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 Mechanism Control unit q0 Input file yes/no Question: What is the difference between a general automaton and a DFA? Transition Graph M = (Q, , , q0, F) |Q| vertices (circles) Edge (qi, qj) labelled a for (qi, a) = qj Initial vertice q0 Final vertices (double circles) in F Example 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 q0 q1 1 q2 1 0 0 0 1 Example 1 2 3 Letter Digit Letter or Digit Letter or Digit 2 Extended Transition Function *(q, ) = q *(q, wa) = ( *(q, w), a) Example : (q0, a) = q1 & (q1, b) = q2 *(q0, ab) = q2 Languages and DFAs M = (Q, , , q0, F) L(M) = {w * | *(q0, w) F} L(M) = {w * | *(q0, w) F} Example M = ({q0, q1, q2}, {a, b}, , q0, {q1}) L(M) = {anb} q0 q1 q2 a, b a, b a b Trap State A state at which the corresponding dfa is unable to stop Can be either final states or not Example : trap state q0 q1 q2 a, b a, b a b Theorem M = (Q, , , q0, F) GM: associated transition graph w + *(qi, w) = qj iff there is a walk labelled w from qi to qj Transition Table A table used to represent an automaton Rows headers: states Columns headers: input symbols Entries: next states Example a b qo qo q1 q1 q2 q2 q2 q2 q2 q0 q1 q2 a, b a, b a b Example L(M) = {w {a, b}* | w starts with ab} q0 q1 q2 b a, b b a trap state q3 a a, b Example 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 L = {awa | w {a, b}*} q0 q2 q3 b a b a trap state q1 a a, b b .