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 # 32 Theory Of Automata By Dr. MM Alam 1 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 Whether or not the given CFG generates any word? Problem of emptiness of CFL. To determine whether the nonterminal X is ever used in the derivation of word from the given CFG? Problem of usefulness. 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 A a, C b, it can be written as 5 S aB A BSB A bb B aaS B bb C SS B bb and A bb, it can be written as: 6 S AB, A BSB, B CC C SS A a|b C b|bb S abb A bbSbb B aaS C SS Since S abb has been obtained so, abb is a | Lecture # 32 Theory Of Automata By Dr. MM Alam 1 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 Whether or not the given CFG generates any word? Problem of emptiness of CFL. To determine whether the nonterminal X is ever used in the derivation of word from the given CFG? Problem of usefulness. 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 A a, C b, it can be written as 5 S aB A BSB A bb B aaS B bb C SS B bb and A bb, it can be written as: 6 S AB, A BSB, B CC C SS A a|b C b|bb 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 determined. Z is unproductive nonterminal, so eliminating the productions involving Z. S Aba|b A Xb B bAA X aaa S Aba | bAZ | b A Xb | bZa B bAA X aZa|aaa Z ZAbA 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 A Xb .