TAILIEUCHUNG - Lecture note Theory of automata - Lecture 9

In this chapter, you will learn to: TGs accepting the languages: Containing aaa or bbb, beginning and ending in different letters, beginning and ending in same letters, EVEN-EVEN, a’s occur in even clumps and ends in three or more b’s, example showing different paths traced by one string, definition of GTG. | Lecture # 18 Theory Of Automata By Dr. MM Alam 1 1 Lecture 17 Recap . Regular Languages Introduction – Repeat Intersection with another language also results in a regular language 2 Theorem 12 – Repeat Statement The set of regular languages is closed under intersection. If L1 and L2 are regular languages then L1∩ L2 is also a regular language. 3 Theorem 12 – Repeat PROOF: By Demorgan’s Law For sets of any kind (regular or not) L1∩L2 = (L1' + L2')‘ L1∩L2 consists of all words that are not in L1’ or L2’. Because L1 is regular then L1’ is also regular (using Theorem 11) and so as L2’ is regular Also L1' + L2' is regular, therefore (L1' + L2')‘ is also regular (using Theorem 11) 4 Theorem 12 – Repeat Two languages over Σ = {a,b} L1 = all strings with a double a L2 = all strings with an even number of a's. L1 and L2 are not the same, since aaa is in L1 but not in L2 and aba in in L2 but not in L1 Example 5 Theorem 12 – Repeat L1 and L2 are regular languages defined by the regular .

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Generalized transition graphs
• Definition of GTG
• 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