1. Lecture # 8 Theory Of Automata By Dr. MM Alam
2. 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
3. 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!
4. • Example for FA that does not end at bb only. – RE will be as :- Λ+a+b+(a+b)*(ab+ba+aa)
5. • 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
6. Even-Even Example • Even-Even Example cannot be modeled using Martin’s method.
7. 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
8. • Starting and ending in different letters
9. • Ends at a double letter
10. GTG Example
11. 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
12. 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
13. 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 various states and convert it to a single state or single transition GTG, so that we can get the regular expression associated with the TG.
14. Steps involved in TG to GTG conversion Examples taken from Daniel I Cohen Book • Step I: More than one Initial states conversion:
15. • Step II: More than one Final states conversion:
16. • Step III: Multiple Loops conversion: r3 5 r4
17. • Step IV: State Elimination:
18. Lecture 8 Summary • Martin View of FA • 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)