tailieunhanh - Lecture note Theory of automata - Lecture 17

Lecture Theory of automata - Lecture 17 includes the following content: Converting NFA to FA (method 3), example, NFA and Kleene’s theorem method 1, examples, NFA and Kleene’s theorem method 2 , NFA corresponding to union of FAs, example. | Lecture # 26 Theory Of Automata By Dr. MM Alam 1 1 Lecture 25 Summary Regular Grammar conversion to FA JFLAP Practical demonstration Elimination of NULL Productions Elimination of UNIT Productions 2 Eliminate Unit Productions EXAMPLE Consider S → A Ibb A → B Ib B → S | a Separate the units from the nonunits:. Unit Production Other ones S → A S → bb A → B A → b B → S B → a 3 Killing Unit Productions S → A gives S → b S → A → B gives S → a A → B gives A → a A → B → S gives A → bb B → S gives B → bb B → S → A gives B → b 4 S → A Ibb A → B Ib B → S | a Introduction to Chomsky Normal form If L is a language generated by some CFG, then there is another CFG that generates all the non-ʎ words of L, all of whose productions are of one of two basic forms: string of only Nonterminals or Nonterminal - one terminal 5 Introduction to Chomsky Normal form Example 1 Let start with the CFG: S → X I X2aX2 aSb I b Xl → X2X2 I b X2 → aX2 I aaX1 After the conversion we have: S → X1 X1 → X 2X | Lecture # 26 Theory Of Automata By Dr. MM Alam 1 1 Lecture 25 Summary Regular Grammar conversion to FA JFLAP Practical demonstration Elimination of NULL Productions Elimination of UNIT Productions 2 Eliminate Unit Productions EXAMPLE Consider S → A Ibb A → B Ib B → S | a Separate the units from the nonunits:. Unit Production Other ones S → A S → bb A → B A → b B → S B → a 3 Killing Unit Productions S → A gives S → b S → A → B gives S → a A → B gives A → a A → B → S gives A → bb B → S gives B → bb B → S → A gives B → b 4 S → A Ibb A → B Ib B → S | a Introduction to Chomsky Normal form If L is a language generated by some CFG, then there is another CFG that generates all the non-ʎ words of L, all of whose productions are of one of two basic forms: string of only Nonterminals or Nonterminal - one terminal 5 Introduction to Chomsky Normal form Example 1 Let start with the CFG: S → X I X2aX2 aSb I b Xl → X2X2 I b X2 → aX2 I aaX1 After the conversion we have: S → X1 X1 → X 2X 2 S → X2AX 2 X1 → B S → ASB X2 → AX 2 S → B X2 → AAX1 A → a B → b 6 Introduction to Chomsky Normal form Example 1 We have not employed the disjunction slash I but instead have written out all the productions separately so that we may observe eight of the form: Nonterminal → string of Nonterminals and two of the form: Nonterminal → one terminal 7 Introduction to Chomsky Normal form EXAMPLE 2 Why not simply replace all a's in long strings by this Nonterminal? For instance, why cannot S → Na N → alb become S → NN N → a l b What do you think? 8 EXAMPLE 2 The answer is that bb is not generated by the first grammar but it is by the second. The correct modified form is S → NA N → alb A → a 9 Introduction to Chomsky Normal form EXAMPLE 3 The CFG S → XY X → XX Y → YY Y → a Y → b (which generates aa*bb*), 10 Introduction to Chomsky Normal form EXAMPLE 3 With our algorithm, become: S → XY X → XX y → yy X → A Y → B A → a B → b 11 Introduction to Chomsky Normal form EXAMPLE With our algorithm, .

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Solution of the task
• Kleene’s theorem
• 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
• 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