tailieunhanh - Lecture note Theory of automata - Lecture 1

In this chapter, students will be able to understand: Introduction to the course title, Formal and Informal languages, Alphabets, Strings, Null string, Words, Valid and In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME. | Lecture # 9 Theory Of Automata By Dr. MM Alam 1 Lecture 8 at a glance How to define FA using Martin Method Which FA’s cannot be modeled using Martin’s method TG and GTG Definition and Examples Kleene Theorem Introduction Kleene Theorem Part I and Part II (Till State elimination) State elimination cont’d 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. 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 During | Lecture # 9 Theory Of Automata By Dr. MM Alam 1 Lecture 8 at a glance How to define FA using Martin Method Which FA’s cannot be modeled using Martin’s method TG and GTG Definition and Examples Kleene Theorem Introduction Kleene Theorem Part I and Part II (Till State elimination) State elimination cont’d 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. 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 During the process, any state encountered final, the resultant state will be final. This is due to the fact that multiple final states are allowed in FA. Question Find FA1 U FA2 for the following: Question Find FA1 U FA2 for the following: Old States Reading at a Reading at b z1-≡(x1,y1) (x2,y2)≡z2 (x5,y4)≡z3 z2≡(x2,y2) (x3,y2)≡ z4 (x6,y3)≡z5 z3+≡(x5,y4) (x6,y5)≡ z6 (x6,y4)≡z7 z4≡(x3,y2) (x4,y2)≡ z8 (x6,y3)≡z5 z5+≡(x6,y3) (x6,y2)≡ z9 (x6,y3)≡z5 Old States Reading at a Reading at b z6+≡(x6,y5) (x6,y5)≡ z6 (x6,y4)≡z7 z7≡(x6,y4) (x6,y5)≡ z6 (x6,y4)≡z7 z8+≡(x4,y2) (x4,y2)≡ z8 (x4,y3)≡z10 z9≡(x6,y2) (x6,y2)≡ z9 (x6,y3)≡z5 z10+≡(x4,y3) (x4,y2)≡ z8 (x4,y3)≡z10 Lecture 9 Summary Kleene Theorem Part I and Part II (Till State elimination) Kleene Theorem Part III (Union) Lecture # 10 Theory Of Automata By Dr. MM Alam 18 Lecture 9 at a glance Kleene Theorem Part I and Part II (Till State elimination) Kleene Theorem Part III (Union) Kleene Theorem Part III (Concatenation) If r1r2 represents a regular .