tailieunhanh - Lecture Theory of automata - Lecture 44

In this chapter, the following content will be discussed: Decidability, whether a CFG generates certain string (emptiness), examples, whether a nonterminal is used in the derivation of some word (uselessness), examples, whether a CFL is finite (finiteness), example, whether the given string is generated by the given CFG (membership), example, parsing techniques, top down parsing, example. | Decidablity Following are the decidable problems . CFG Whether or not the given CFG generates any word? Problem of emptiness of CFL. Whether or not the given CFG generates the finite language? Problem of finiteness. 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 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 | Decidablity Following are the decidable problems . CFG Whether or not the given CFG generates any word? Problem of emptiness of CFL. Whether or not the given CFG generates the finite language? Problem of finiteness. 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 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. 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): Find all unproductive nonterminals (the nonterminal is unproductive if it cannot produce a string of terminals). Eliminate all productions involving unproductive nonterminals. Paint all X’s blue. 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