tailieunhanh - Lecture note Theory of automata - Lecture 23

The main contents of this chapter include all of the following: Mealy machines in terms of sequential circuit, equivalent machines, moore equivalent to mealy, proof, example, mealy equivalent to moore, proof, example. | Lecture note Theory of automata - Lecture 23 Lecture 32 Theory Of Automata By Dr. MM Alam 1 Lecture 31 at a glance. Non Context Free Languages How to determine Non Context Free languages Pumping Lemma for Non Context Free Languages JFLAP For Pumping Lemma for Non Context Free Languages 2 JFLAP for Context Free Pumping Lemma Repeat Decidability In this chapter we will focus on three problems 1. Whether or not the given CFG generates any word Problem of emptiness of CFL. 2. To determine whether the nonterminal X is ever used in the derivation of word from the given CFG Problem of usefulness. 3. Whether or not the given CFG generates the finite language Problem of finiteness. 4 Whether or not the given CFG generates any word Problem of emptiness of CFL. Consider the following Example S AB A BSB B CC C SS A a b C b bb 5 S aB S AB A BSB B CC C SS A a b A BSB C b bb A bb B aaS B bb C SS B bb and A bb it can be written as 6 S abb A bbSbb B aaS C SS Since S abb has been obtained so abb is a word in the corresponding CFL. 7 To determine whether the nonterminal X is ever used in the derivation of word from the given CFG Problem of usefulness. Consider the following CFG S Aba bAZ b A Xb bZa B bAA X aZa aaa Z ZAbA 8 To determine whether X is ever used to generate some words unproductive nonterminals are S Aba bAZ b determined. Z is A Xb bZa B bAA unproductive nonterminal X aZa aaa so eliminating the Z ZAbA productions involving Z. S Aba b A Xb B bAA X aaa 9 X points to non terminal so A also. Thus B and S also point to non terminal. So only useful productions shall be used. 10 Whether or not the given CFG generates the finite language Problem of finiteness. Example Consider the CFG S ABa bAZ b A Xb bZa B bAA X aZa bA aaa Z ZAbA Here the nonterminal Z is useless so by eliminating we get the following grammar 11 S ABa b A Xb B bAA X bA aaa Starting with nonterminal X. It is self- embedded therefore the grammar creates an infinite language. S ABa b 12 Example Consider the .