TAILIEUCHUNG - 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

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• The language of strings
• Automata theory
• Automata theory languages
• Automata theory computation
• Pushdown automata
• Context Free grammars
• Regular languages
• Additional classes
• Intractable problems
• Properties of context free languages
• Solution of the task
• Polish notation
• Total language tree
• Null production
• Nullable production
• Theorem regarding CNF
• The START state
• Nondeterministic PDA
• Equivalent PDA
• PDA corresponding to CFG
• STACK alphabet
• Computer science
• CFG corresponding
• Conversion form of PDA
• Recap of PDA
• Non context free language
• Parsing techniques
• Turing machine
• DELETE subprogram
• Kleene’s theorem
• NFA corresponding
• Concatenation of FAs
• Distinguishable strings
• Indistinguishable strings
• Recap theorem
• Moore machine
• Mealy machine
• Applications of complementing
• Equivalent machines
• Mealy machines
• Complement of a language
• Non regular language
• Example of nonregular language
• Pumping lemma version I