Lecture Theory of automata - Lecture 24 includes the following content: Regular languages, complement of a language, theorem, proof, example, intersection of two regular languages. | Lecture note Theory of automata - Lecture 24 Lecture 10 Theory Of Automata By Dr. MM Alam 1 Lecture 9 at a glance Kleene Theorem Part I and Part II Kleene Theorem Part III Union 2 Repeat Kleene Part III Every Regular Expression can be represented by an FA We already know that a regular expression has a corresponding FA. However the difficult part is that a regular expression can be combined with other regular expression through union sum concatenation and closure of FA. Thus we need to devise methods for FA1 FA2 FA1FA2 FA1 Closure. 3 Repeat Kleene Theorem Part III Union If r1 r2 represents a regular expression r3 then FA FA2 represents an FA3 that correspond to r3. Start by taking both FA s initial state and traversing on each input symbol in the respective FA Since one initial state is allowed in FA therefore only one state can be marked as initial state 4 Old States Reading at a Reading at b z1- q0 p0 q1 p1 z2 q1 p1 z2 z2 q1 p1 q3 p1 z3 q2 p1 z4 z3 q3 p1 q3 p1 z3 q3 p1 z3 z4 q2 p1 q2 p1 z4 q2 p1 z4 5 6 Kleene Theorem Part III Concatenation If r1r2 represents a regular expression r3 then FA1FA2 represents an FA3 that should correspond to r3. Start by taking the first FA s initial state and traversing on each input symbol in the respective FA. Since one initial state is allowed in FA therefore only one state can be marked as initial state 7 3 Questions for Concatenation FA1 a b b a b FA2 a b FA3 aaa b 8 Question concatenation Find FA1FA2 for the following 9 10 Verification a b b a b a b bba 11 Question concatenation Find FA2FA1 for the following 12 Old States Reading at a Reading at b z1- p0 p1 q0 z2 p1 q0 z2 z2 p1 q0 p1 q0 q1 z3 p1 q0 q1 z3 z3 p1 q0 q1 p1 q0 q1 q3 z4 p1 q0 q1 q2 z5 z4 p1 q0 q1 q3 p1 q0 q1 q3 q3 p1 q0 q1 q2 q3 z6 p1 q0 q1 q3 z4 z5 p1 q0 q1 q2 p1 q0 q1 q2 q2 p1 q0 q1 q2 q3 z6 p1 q0 q1 q2 z5 z6 p1 q0 q1 q2 q p1 q0 q1 q2 q2 q3 3 p1 q0 q1 q3 q2 q3 p1 q0 q1 q2 q3 z6 p1 q0 q1 q2 q3 z6 13 Verification a b a b b a b aabaaa 14 Question concatenation Find
