tailieunhanh - 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 . | 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 expressions below. r1 = (a + b)*aa(a + b)* r2 = b*(ab*ab*)* A word in L2 can have some b’s in the front But whenever there is an a, it balanced by an other a (after some b’s). Gives the factor of the form (ab*ab*) The words can have as many factors of this from as it wants. It can end an a or ab. Example 6 Theorem 12 – Repeat These two languages can also be defined by FA (Kleen’s theorem) Example FA1 FA2 7 Theorem 12 – Repeat In the proof of the theorem that the complement of a regular language is regular an algorithm is given for building the machines that accept these languages. Now reverse what is a final state and what is not a final state. The machines for these languages are then (see the next slide ) 8 Theorem 12 – Repeat Recall that how we go through stages of transition graphs with edges labeled by regular expressions. Thus, FA1' becomes: 9 Theorem 12 State q3 is part of no path from - to +, so it can be dropped. We need to join incoming a edge with both outgoing edges(b to q1 and q2

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Generalized transition graphs
• Definition of GTG
• Formal Languages & Automata
• Pushdown Automata
• Finite Automata
• Non deterministic Pushdown Automata
• Instantaneous Description
• Language accepted by NPDA
• Deterministic Finite Automata (DFA)
• Operational Manner
• Transition Graphs
• Extended Transition Function
• Automata theory
• Automata theory languages
• Automata theory computation
• Context Free grammars
• Regular languages
• Automata hữu hạn
• Đoán nhận ngôn ngữ
• Biểu diễn automata
• Xây dựng automata
• xây dựng DFA
• Automata Model
• Settlement Development
• Automata Framework
• Cellular Automata
• Transport Equations
• Population Dynamics
• isaster Areas
• Bus Dynamics
• A Hierarchy of Formal Languages and Automata
• ecursively Enumerable Languages
• Recursive Languages
• Unrestricted Grammars
• Context Sensitive Grammars
• Tin học lý thuyết
• Bài giảng Tin học lý thuyết
• Automata đẩy xuống
• Push Down Automata
• PDA đơn định
• PDA không đơn định
• Additional classes
• Intractable problems
• Properties of context free languages
• Introduction to automata theory languages and compution
• Regular expressions
• Properties of regular sets
• chương trình đồ họa
• giáo trình thiết kế
• thiết kế đồ họa
• lý thuyết automata
• tài liệu về automata
• tài liệu về pushdown automata
• ngôn ngữ lập trình
• Logical Computation
• Quantum Computations
• Automata Application
• Organizing Networks
• Molecular Orbitals
• Disordered Cellular automata
• Traffic flow models
• Automata traffic
• Nagel Schreckenberg
• Deceleration terms
• Cellular Automata in transportation
• Evaluating Dynamic
• Three Basic Concepts
• Languages Grammars Automata
• Input file
• Control unit
• String in L
• Introduction Formal Languages & Automata
• A formal language
• An automaton
• Fundamental ideas
• Models underlying computing
• Văn phạm phi ngữ cảnh
• Ngôn ngữ hình thức
• Văn phạm hình thức và các Automata
• Trình biên dịch
• 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