tailieunhanh - Lecture note Theory of automata - Lecture 4

This chapter includes contents: Regular expression of EVEN-EVEN language, Difference between a* + b* and (a+b)*, Equivalent regular expressions; sum, product and closure of regular expressions; regular languages, finite languages are regular, introduction to finite automaton, definition of FA, transition table, transition diagram. | Lecture # 13 Theory Of Automata By Dr. MM Alam 1 1 Lecture 12 at a glance NFA with NULL to FA Conversion using transition tables Examples 2 NFA with NULL conversion – Repeat 3 a b z1 ≡ 1 (1,2,4) ≡ z2 ᵩ ≡ Z5 Z2+ ≡ (1,2,4) (1,2,4) ≡ z2 (1,3,4) ≡ z3 Z3+ ≡ (1,3,4) (1,2,4,3) ≡ z4 (1,3,4) ≡ z3 Z4+ ≡ (1,2,3,4) (1,2,4,3 )≡ z4 (1,3,4) ≡ z3 4 a b Z1 ≡ 1 (1,2,4) ≡ Z2 ᵩ ≡ Z5 Z2+ ≡ (1,2,4) (1,2,4) ≡ z2 (1,3,4) ≡ z3 Z3+ ≡ (1,3,4) (1,2,4,3) ≡ z4 (1,3,4) ≡ z3 Z4+ ≡ (1,2,3,4) (1,2,4,3 )≡ z4 (1,3,4) ≡ z3 5 Convert the following NFA with NULL transition to FA. 6 7 Which conversion from NFA-with NULL to NFA is OK? a b Question: a b qo ≡ z1 (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 Z2 ≡ (qo, q1, q2) (qo, q1, q2, q3) ≡ Z4 ( q1, q3) ≡ Z3 Z3+ ≡ ( q1, q3) ( q1, q3) ≡ Z3 ( q0, q2) ≡Z5 Z4+ ≡ (qo, q1, q2, q3) (qo, q1, q2, q3) ≡ Z4 (q1, q3, q2, q0) ≡ Z4 Z5 ≡ (qo, q2) (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 8 a b qo ≡ z1 (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 Z2 ≡ (qo, q1, q2) (qo, q1, q2, q3) ≡ Z4 ( q1, q3) ≡ Z3 Z3+ ≡ ( q1, . | Lecture # 13 Theory Of Automata By Dr. MM Alam 1 1 Lecture 12 at a glance NFA with NULL to FA Conversion using transition tables Examples 2 NFA with NULL conversion – Repeat 3 a b z1 ≡ 1 (1,2,4) ≡ z2 ᵩ ≡ Z5 Z2+ ≡ (1,2,4) (1,2,4) ≡ z2 (1,3,4) ≡ z3 Z3+ ≡ (1,3,4) (1,2,4,3) ≡ z4 (1,3,4) ≡ z3 Z4+ ≡ (1,2,3,4) (1,2,4,3 )≡ z4 (1,3,4) ≡ z3 4 a b Z1 ≡ 1 (1,2,4) ≡ Z2 ᵩ ≡ Z5 Z2+ ≡ (1,2,4) (1,2,4) ≡ z2 (1,3,4) ≡ z3 Z3+ ≡ (1,3,4) (1,2,4,3) ≡ z4 (1,3,4) ≡ z3 Z4+ ≡ (1,2,3,4) (1,2,4,3 )≡ z4 (1,3,4) ≡ z3 5 Convert the following NFA with NULL transition to FA. 6 7 Which conversion from NFA-with NULL to NFA is OK? a b Question: a b qo ≡ z1 (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 Z2 ≡ (qo, q1, q2) (qo, q1, q2, q3) ≡ Z4 ( q1, q3) ≡ Z3 Z3+ ≡ ( q1, q3) ( q1, q3) ≡ Z3 ( q0, q2) ≡Z5 Z4+ ≡ (qo, q1, q2, q3) (qo, q1, q2, q3) ≡ Z4 (q1, q3, q2, q0) ≡ Z4 Z5 ≡ (qo, q2) (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 8 a b qo ≡ z1 (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 Z2 ≡ (qo, q1, q2) (qo, q1, q2, q3) ≡ Z4 ( q1, q3) ≡ Z3 Z3+ ≡ ( q1, q3) ( q1, q3) ≡ Z3 ( q0, q2) ≡Z5 Z4+ ≡ (qo, q1, q2, q3) (qo, q1, q2, q3) ≡ Z4 (q1, q3, q2, q0) ≡ Z4 Z5 ≡ (qo, q2) (qo, q1, q2) ≡ Z2 ( q1, q3) ≡ Z3 10 Task Solution for FA Closure Old States Reading at a Reading at b z1±≡q0 q1≡z2 q2≡z3 z2 ≡q1 q1≡z2 (q3, q0)≡z4 z3 ≡q2 (q4, q0)≡z5 q2≡z3 z4+≡ (q3, q0) (q1,q1)≡q1≡z2 (q3, q0,q2)≡z6 z5+≡ (q4, q0) (q1,q4,q0)≡z7 (q2,q2)≡q2≡z3 z6+≡ (q3, q0,q2) (q1,q1,q4,q0)≡(q1,q4,q0)≡z7 (q3, q0,q2,q2)≡ (q3, q0,q2)≡z6 z7+≡ (q1,q4,q0) (q1,q4,q0,q1)≡(q1,q4,q0)≡z7 (q3, q0,q2,q2)≡ (q3, q0,q2)≡z6 Verification: ( a(a+b)*b + b(a+b)*a)* A,b,abba,baab,aaaabbbbba, 11 Finite Automata with output In Finite Automata, the input string represents the input data to a computer program. Reading the input letters is very much similar to how a computer program performs various instructions. The concept of states tell us that what we are printing and what we have printed so far. 12 Summary Lecture#13 NFA conversion – Repeat Closure Task Solution .