tailieunhanh - Lecture note Theory of automata - Lecture 3

This chapter includes contents: RE, Recursive definition of RE, defining languages by RE, { x}*, { x}+, {a+b}*, language of strings having exactly one aa, Language of strings of even length, language of strings of odd length, RE defines unique language (as Remark), language of strings having at least one a, language of strings havgin at least one a and one b, Language of strings starting with aa and ending in bb, Language of strings starting with and ending in different letters. | Lecture # 12 Theory Of Automata By Dr. MM Alam 1 1 Lecture 11 at a glance Kleene Theorem Part III (Concatenation) Examples of Kleene Theorem Concatenation part. Closure and its Examples 2 NFA & FA at a glance FA NFA Single Start State and multiple end states (may be none) Single Start State and multiple end states (may be none) Finite set of input symbols Same Finite set of transitions Same Deterministic Non-Deterministic Distinguishing Rule No such rule 3 Example Consider the following NFA 4 Example A simple NFA that accepts the language of strings defined over ={a,b}, consists of bb and bbb The above NFA can be converted to the following FA b 5 Example Continued . 6 7 NFA with Null Transition Convert the following NFA with NULL transition to FA. 8 9 a b z1 ≡ qo (qo, q1) ≡ z2 ᵩ ≡ z3 z2 ≡ (qo, q1) (qo, q1) ≡ z2 (q1, q2) ≡ z4 z4+≡ (q1, q2) q3 ≡ z5 (q1, q2) ≡ z4 z5+≡ q3 q3 ≡ z5 q1 ≡ z6 z6≡ q1 ᵩ ≡ z3 (q1, q2) ≡ z4 10 a b z1 ≡ qo (qo, q1) ≡ z2 ᵩ ≡ z3 z2 ≡ (qo, q1) (qo, q1) ≡ z2 | Lecture # 12 Theory Of Automata By Dr. MM Alam 1 1 Lecture 11 at a glance Kleene Theorem Part III (Concatenation) Examples of Kleene Theorem Concatenation part. Closure and its Examples 2 NFA & FA at a glance FA NFA Single Start State and multiple end states (may be none) Single Start State and multiple end states (may be none) Finite set of input symbols Same Finite set of transitions Same Deterministic Non-Deterministic Distinguishing Rule No such rule 3 Example Consider the following NFA 4 Example A simple NFA that accepts the language of strings defined over ={a,b}, consists of bb and bbb The above NFA can be converted to the following FA b 5 Example Continued . 6 7 NFA with Null Transition Convert the following NFA with NULL transition to FA. 8 9 a b z1 ≡ qo (qo, q1) ≡ z2 ᵩ ≡ z3 z2 ≡ (qo, q1) (qo, q1) ≡ z2 (q1, q2) ≡ z4 z4+≡ (q1, q2) q3 ≡ z5 (q1, q2) ≡ z4 z5+≡ q3 q3 ≡ z5 q1 ≡ z6 z6≡ q1 ᵩ ≡ z3 (q1, q2) ≡ z4 10 a b z1 ≡ qo (qo, q1) ≡ z2 ᵩ ≡ z3 z2 ≡ (qo, q1) (qo, q1) ≡ z2 (q1, q2) ≡ z4 z4+≡ (q1, q2) q3 ≡ z5 (q1, q2) ≡ z4 z5+≡ q3 q3 ≡ z5 q1 ≡ z6 z6≡ q1 ᵩ ≡ z3 (q1, q2) ≡ z4 11 Convert the following NFA with NULL transition to FA. 12 13 a b z1- ≡ 1 (2,5) ≡ z2 3,4 ≡ z3 Z2+ ≡ ( 2,5) 4 ≡ z ᵩ ≡ Z5 Z3 ≡ (3,4) (2,5,4) ≡ z6 4 ≡ z4 Z4 ≡ 4 (4,5) ≡ z7 ᵩ ≡ Z5 Z5 ≡ ᵩ Z5 Z5 Z6+ ≡ (2,5,4) (4,4) ≡ z4 ᵩ ≡ Z5 Z7+ ≡ (4,5) (4,5) ≡ z7 ᵩ ≡ Z5 14 15 Convert the following NFA with NULL transition to FA. 16 17 a b z1+ ≡ 1 (3,4) ≡ z2 ᵩ ≡ Z3 Z2+ ≡ (3,4) (3,4) ≡ z2 ᵩ ≡ Z3 Z3 ≡ ᵩ Z3 Z3 18 19 20 21 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 22 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 23 Lecture#12 Summary NFA to FA manual conversion NFA with NULL to FA Conversion using transition tables Examples .