Lecture Theory of Automata: Lesson 44. The main topics covered in this chapter include: decidability, whether a CFG generates certain string (emptiness), whether a nonterminal is used in the derivation of some word (uselessness), whether a CFL is finite (finiteness), whether the given string is generated by the given CFG (membership), parsing techniques, top down parsing, . | Decidablity Following are the decidable problems . CFG 1. Whether or not the given CFG generates any word Problem of emptiness of CFL. 2. Whether or not the given CFG generates the finite language Problem of finiteness. 3. Whether or not the given string w can be generated by the given CFG Problem of membership. Following are algorithms showing that the answers to the above three questions are yes. Algorithm 1 Emptiness If the given CFG contains a production of the form S then obviously the corresponding CFL is not empty. If the CFG contains the production of the form S t where t is a terminal or string of terminal then t is a word of the corresponding CFL and CFL is not empty. If the CFG contains no such production then 1. For each nonterminal N with N t pick one production for N if there are more than one and replace N by t in the right side of each production wherever it lies. Remove all such productions from the CFG. Doing so the CFG will be changed it will generate atleast one word of the old CFL. 2. Repeat the process until either it eliminates S or no new nonterminal is eliminated. If S has been eliminated then CFG generates some words otherwise not. Following is an example Example S AB A BSB B CC C SS A a b C b bb Step 1 . Picking A a C b it can be written as S aB A BSB A bb B aaS B bb C SS Step 1 . Picking B bb and A bb it can be written as S abb A bbSbb B aaS C SS Since S abb has been obtained so abb is a word in the corresponding CFL. To determine whether the nonterminal X is ever used in the derivation of word from the given CFG following algorithm is used Algorithm 2 Uselessness 1. Find all unproductive nonterminals the nonterminal is unproductive if it cannot produce a string of terminals . 2. Eliminate all productions involving unproductive nonterminals. 3. Paint all X s blue. 4. If any nonterminal is in the left side of the production with any blue nonterminal in the right side paint that nonterminal blue and paint that nonterminal blue at all
