tailieunhanh - Lecture note Theory of automata - Lecture 15

After studying this chapter you will be able to understand: Examples of Kleene’s theorem part III (method 3), NFA, examples, avoiding loop using NFA, example, converting FA to NFA, examples, applying an NFA on an example of maze. | Lecture # 24 Theory Of Automata By Dr. MM Alam 1 1 Lecture#23 Summary CFG Examples Introduction to Trees Ambiguity in CFGs CFG in JFLAP Unrestricted Grammars Unrestricted Grammars: An unrestricted grammar is similar to a context-free grammar (CFG), except that the left side of a production may contain any nonempty string of terminals and variables, rather than just a single variable. In a CFG, the single variable on the left side of a production could be expanded in a derivation step. In an unrestricted grammar, multiple variables and/or terminals that match the left-side of a production can be expanded by the right-side of that production. 3 Unrestricted Grammar Example S AX Db bD A aAbc DX EXc A aBbc BX ʎ Bb bB cE Ec 4 CFG with JFLAP Unrestricted Grammar with JFLAP User Controlled Parsing with JFLAP 5 Semi words Definition For a given CFG a semiword is a string of terminals (maybe none) concatenated with exactly one nonterminal (on the right), for example, (terminal) | Lecture # 24 Theory Of Automata By Dr. MM Alam 1 1 Lecture#23 Summary CFG Examples Introduction to Trees Ambiguity in CFGs CFG in JFLAP Unrestricted Grammars Unrestricted Grammars: An unrestricted grammar is similar to a context-free grammar (CFG), except that the left side of a production may contain any nonempty string of terminals and variables, rather than just a single variable. In a CFG, the single variable on the left side of a production could be expanded in a derivation step. In an unrestricted grammar, multiple variables and/or terminals that match the left-side of a production can be expanded by the right-side of that production. 3 Unrestricted Grammar Example S AX Db bD A aAbc DX EXc A aBbc BX ʎ Bb bB cE Ec 4 CFG with JFLAP Unrestricted Grammar with JFLAP User Controlled Parsing with JFLAP 5 Semi words Definition For a given CFG a semiword is a string of terminals (maybe none) concatenated with exactly one nonterminal (on the right), for example, (terminal) (terminal) . . . (terminal) (Nonterminal) 6 What are semi words? DEFINITION A CFG is called a regular grammar if each of its productions is of one of the two forms Nonterminal → semiword or Nonterminal → word 7 Semiwords Relationship between regular languages and context-free grammars? All regular languages can be generated by CFG's, and so can some nonregular languages but not all possible languages. Some regular languages can be generated by CFG's and some regular languages cannot be generated by CFG's. Some nonregular languages can be generated by CFG's and some nonregular languages cannot. 8 FA Conversion to Regular grammar Accepts the language of all words with a double a: S →aM S →bS M →aF M →bS F →aF F →bF F →ʎ 9 FA Conversion to Regular grammar Example 1 The word babbaaba is Accepted by FA Through sequence of this semi paths. 10 S S→bS bS S→aM baM M→bS babS S→bS babbS S→aM babbaM M→aF babbaaF F→bF babbaabF F→aF babbaabaF F→λ babbaaba FA Conversion to Regular grammar Example .

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Kleene’s theorem part III
• Nondeterministic finite automaton
• 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