tailieunhanh - Lecture note Theory of automata - Lecture 8

Lecture Theory of automata - Lecture 8 presents the following content: TG definition, Examples: accepting all strings, accepting none, starting with b, not ending in b, containing aa, containing aa or bb. | Lecture # 17 Theory Of Automata By Dr. MM Alam 1 1 Lecture 16 Recap . Transducers Example 2 Regular Languages Introduction Regular Languages Union, Concatenation, Closure also results in a regular language Complement of a regular language and Intersection with another language also results in a regular language 2 Theorem 12 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 3 Theorem 12 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 4 Theorem 12 These two languages can also be defined by FA (Kleen’s theorem) Example FA1 FA2 | Lecture # 17 Theory Of Automata By Dr. MM Alam 1 1 Lecture 16 Recap . Transducers Example 2 Regular Languages Introduction Regular Languages Union, Concatenation, Closure also results in a regular language Complement of a regular language and Intersection with another language also results in a regular language 2 Theorem 12 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 3 Theorem 12 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 4 Theorem 12 These two languages can also be defined by FA (Kleen’s theorem) Example FA1 FA2 5 Theorem 12 In the first machine we stay in the start state until we read our first a. Then we move to the middle state. Here we can find a double a. If we read another a from the input string while in the middle state, we move to the final state where we remain. If we read a b, we go back to -. If we never get past the middle state, the word has no double a and is rejected. Example 6 Theorem 12 The second machine switches from left state to right state or from right state to left state every time it reads an a. It ignores all b's. If the string begins on the left and ends on the left, it must have made an even number of left/right switches. Therefore, the strings this machine accepts are exactly those in L2 . Example 7 Theorem 12 The first step in building the machine (and regular expression) for L1∩L2 is to find the machines that accept the complementary languages L1' and L2'. The English description of these languages is: L1' = all strings that do not contain the substring a L2' =

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• TG definition
• Accepting none
• 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