tailieunhanh - Lecture note Theory of automata - Lecture 22

The following will be discussed in this chapter: Applications of complementing and incrementing machines, equivalent machines, moore equivalent to mealy, proof, example, mealy equivalent to moore, proof, example. | Lecture note Theory of automata - Lecture 22 Lecture 31 Theory Of Automata By Dr. MM Alam 1 Lecture 30 at a glance Using JFLAP for PDA PDA Conversion to CFG Chomsky Normal Form Conversion in JFLAP 2 What are Non-Context-Free languages All languages are not CFL. Languages which are not Context-Free are called Non-CFL. This chapter is about proving that all languages are not Context-Free We will also use the Pumping Lemma with and without JFLAP for the proof of the aforementioned fact. 3 Live Production VS Dead Production Definition A production of the form nonterminal string of two nonterminals is called a live production. A production of the form nonterminal terminal is called a dead production. 4 Live Productions Example Thanks to Daniel I Cohen. The above excerpts have been taken from his Book Automata Theory Chapter Non Context Free Languages. 5 Finite many words can be generated if a CFG is in CNF and if there is restriction to use the live production at most once each. It may be noted that every time a live production is applied during the derivation of a word it increases the number of non- terminals by one similarly dead productions are applied it decreases the number of non-terminals by one. 6 Self Embedded Nonterminal A nonterminal is said to be self-embedded if in a given derivation of a word it ever occurs as a tree descendant of itself 7 Theorem 33 Statement If a CFG is in CNF with p live and q dead productions and if w is a word generated by the CFG having more than 2p letters then any derivation tree for w has a nonterminal z which is used twice where the second z is the descended from the first z. 8 The nonterminal X is self- embedded 9 Example Grammar S AX X SA S BY Y SB S a S b S AA S BB A a B b 10 S S AX AX X SA ASA S AX AAXA X SA AASAA S AX AAAXAA X SA AAASAAA A a aAASAAA A a aaASAAA A a aaaSAAA S b aaabAAA A a aaabaAA A a aaabaaA A a aaabaaa 11 Consider the following CFG in CNF and the derivation tree of the word bbabbb S AB A BC C AB A a B b

• Tự động hoá
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Applications of complementing
• Equivalent machines
• 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