tailieunhanh - Lecture note Theory of automata - Lecture 2

This chapter includes contents: Kleene Star Closure, Plus operation, recursive definition of languages, INTEGER, EVEN, factorial, PALINDROME, {anbn}, languages of strings (i) ending in a, (ii) beginning and ending in same letters, (iii) containing aa or bb (iv)containing exactly aa. | Lecture # 11 Theory Of Automata By Dr. MM Alam 1 1 Lecture 10 at a glance Kleene Theorem Part III (Union) – Repeat Kleene Theorem Part III (Union) – Example Kleene Theorem Part III (Concatenation) Kleene Theorem Part III Concatenation Examples 2 Kleene Theorem Part III (Concatenation) – Repeat 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 During the process, any state encountered final of the second FA only, the resultant state will be final. Further, the second FA will be concatenated through first FA’s initial state. However, if the final state of the second FA is encountered, it will not be combined with the first FA. 3 Question (concatenation) Find FA3FA2 for the following: 4 Old States Reading at a Reading at b z1- ≡x1 x2≡ | Lecture # 11 Theory Of Automata By Dr. MM Alam 1 1 Lecture 10 at a glance Kleene Theorem Part III (Union) – Repeat Kleene Theorem Part III (Union) – Example Kleene Theorem Part III (Concatenation) Kleene Theorem Part III Concatenation Examples 2 Kleene Theorem Part III (Concatenation) – Repeat 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 During the process, any state encountered final of the second FA only, the resultant state will be final. Further, the second FA will be concatenated through first FA’s initial state. However, if the final state of the second FA is encountered, it will not be combined with the first FA. 3 Question (concatenation) Find FA3FA2 for the following: 4 Old States Reading at a Reading at b z1- ≡x1 x2≡ z2 (x5,p0)≡ z3 z2 ≡x2 x3≡ z4 x6≡ z5 z3≡(x5,p0) ( x6,p1)≡z6 ( x6,p1)≡z6 z4 ≡x3 ( x4,p0)≡z7 x6≡z5 z5 ≡x6 x6≡z5 x6≡z5 z6+≡( x6,p1) ( x6,p1)≡z6 ( x6,p1)≡z6 z7≡( x4,p0) ( x4,p0,p1)≡ z8 ( x4,p0,p1)≡ z8 z8+≡( x4,p0,p1) ( x4,p0,p1,p1)= ( x4,p0,p1)≡z8 ( x4,p0,p1,p1)= (x4,p0,p1)≡z8 5 6 Kleene Theorem Part III (Closure) If r1 represents a regular expression and r1* the closure of the r1. Similarly, if FA1 corresponds to r1 then FA1* should correspond to closure of r1. Start by taking the first FA’s 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. Further, the initial state is marked final by default, in order to accommodate NULL string. During the process, any state found final, the resultant state will be final. Further, the FA’s initial state will be concatenated through its final state. The new state will be marked as final. Note that, the final state of the FA will always be combined .