1. Lecture # 10 Theory Of Automata By Dr. MM Alam 1
2. Lecture 9 at a glance… • Kleene Theorem Part I and Part II • Kleene Theorem Part III (Union) 2
3. 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
4. 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
5. 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. 6
7. 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
8. 3 Questions for Concatenation FA1: (a+b)b(a+b)* FA2: (a+b)+ FA3: (aaa+b)+ 8
9. Question (concatenation) • Find FA1FA2 for the following: 9
10. 10
11. Verification: (a+b)b(a+b)*(a+b) + bba, 11
12. Question (concatenation) • Find FA2FA1 for the following: 12
13. 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
14. Verification: (a+b)+(a+b)b(a+b)* aabaaa 14
15. Question (concatenation) • Find FA3FA1 for the following: 15
16. Old States Reading at a Reading at b z1- ≡x1 x2≡ z2 (x5,q0)≡z3 z2 ≡x2 x3≡ z4 x6≡ z5 z3 ≡(x5,q0) (x6,q1)≡z6 (x6,q1)≡z6 z4 ≡x3 (x4,q0)≡z7 x6≡ z5 z5 ≡x6 x6≡z5 x6≡z5 z6 ≡( x6,q1) ( x6,q3)≡ z8 ( x6,q2)≡ z9 z7≡( x4,q0) ( x4,q0,q1)≡ z10 ( x4,q0,q1)≡ z10 z8 ≡( x6,q3) ( x6,q3)≡ z8 ( x6,q3)≡ 16 z8
17. z9+≡( x6,q2) ( x6,q2)≡ z9 ( x6,q2)≡ z9 z10 ≡( x4,q0,q1) (x4,q0,q1,q3)≡ z11 (x4,q0,q1,q2)≡ z12 z11≡( x4,q0,q1,q3) (x4,q0,q1,q3,q3)= (x4,q0,q1,q2,q3)≡ (x4,q0,q1,q3)≡ z11 z13 z12+≡( x4,q0,q1,q2) (x4,q0,q1,q2,q3)≡ (x4,q0,q1,q2,q2)= z13 (x4,q0,q1,q2)≡z12 z13+≡( x4,q0,q1,q2, (x4,q0,q1,q3,q2,q3) (x4,q0,q1,q2,q2,q3) q3) = = (x4,q0,q1,q2,q3)≡z1 (x4,q0,q1,q2,q3)≡z1 3 3 17
18. Verification: (aaa+b)+(a+b)b(a+b)* bab 18
19. Question (concatenation) • Find FA3FA2 for the following: 19
20. 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,p1)= 20 ( x4,p0,p1)≡z8 (x4,p0,p1)≡z8