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 # 31 Theory Of Automata By Dr. MM Alam 1 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. Please keep in mind that every CFG in CNF has only aforementioned types of productions. Guess what, are the rules of CNF? 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 | Lecture # 31 Theory Of Automata By Dr. MM Alam 1 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. Please keep in mind that every CFG in CNF has only aforementioned types of productions. Guess what, are the rules of CNF? 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