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 # 8 Theory Of Automata By Dr. MM Alam 1 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 >= 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 (GTGs) Transition Graphs Generalized Transition Graphs Finite number of states same Finite set of input strings same Finite set of | Lecture # 8 Theory Of Automata By Dr. MM Alam 1 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 >= 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 (GTGs) Transition Graphs Generalized Transition Graphs Finite number of states same Finite set of input strings same Finite set of transitions including NULL string Finite set of transitions including NULL string and transitions can represent Regular expressions 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 end states Multiple State States and 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 eliminate its