tailieunhanh - Lecture note Theory of automata - Lecture 32

As in English language any sentence can be expressed by parse tree, so any word generated by the given CFG can also be expressed by the parse tree. This chapter provides knowledge of trees. | Lecture note Theory of automata - Lecture 32 Lecture 8 Theory Of Automata By Dr. MM Alam Lecture 7 Recap FA definition RECAP Wrong FA correction using Regular expressions different possibilities. How to build an FA from scratch What are Dead or Trap states in FA Trap or dead state Example using JFLAP How to avoid Dead States in FA Martin method Make each state label as it progresses based on the input strings. Based on the conditions of the Regular expressions or FA only required states are marked final. Not every FA can be modeled in this way Example for FA that does not end at bb only. RE will be as - Λ a b a b ab ba aa Example for FA that does not end at aba and abb. Also the length of each word gt 3 RE will be as follows - aab aaa bab baa bbb bba Even-Even Example Even-Even Example cannot be modeled using Martin s method. Transition Graphs TGs and Generalized Transition Graphs Transition Graphs Generalized GTGs Transition Graphs Finite number of same states Finite set of input same strings Finite set of Finite set of transitions including transitions including NULL string NULL string and transitions can represent Regular Starting and ending in different letters Ends at a double letter GTG Example Kleene Theorem Daniel I Cohen has divided Kleene Theorem in to three parts Part I Every FA is a TG Part II Every TG has a regular expression Every Regular expression can be represented by a Finite Automata Kleene Theorem Part I Every FA is a TG as well. Please refer to Previous Slides. FA TG Single Start State and Multiple State States and multiple end states multiple end states Finite set of input symbols Same Finite set of transitions Same Deterministic Non-Deterministic Distinguishing Rule No such rule Kleene Theorem Part II Every TG has a regular expression. The prove of this Part requires a systematic algorithm through which a TG can be converted to a GTG in which all transitions are actually regular expressions. Thus we need to transform a TG to a GTG and .