PROBLEMS 1. Decide whether or not the following grammars generate any words using the algorithm of Theorem 42 (p. 403):

[answerhappygod]

Problems 1 Decide Whether Or Not The Following Grammars Generate Any Words Using The Algorithm Of Theorem 42 P 403 1 (411.49 KiB) Viewed 38 times

PROBLEMS 1. Decide whether or not the following grammars generate any words using the algorithm of Theorem 42 (p. 403): 404 (i) SaSa | bSb (ii) S-XY X→SY Y→SX x→a Y→b THEOREM 42 PROOF (iv) S-XS X→YX Y→YY Y→XX Given any CFG, there is an algorithm to determine whether or not it can generate any words at all. X→a (v) S-AB The proof will be by constructive example. We show there exists such an algorithm by pre- senting one. In Theorem 23 of Chapter 13, we showed that every CFG that does not generate A can be written without A-productions. CHAPTER 18 Decidability In that proof, we showed how to decide which nonterminals are nullable. The word A is a word generated by the CFG if and only if S is nullable. We already know how to decide whether the start symbol S is nullable: SA? Therefore, the problem of determining whether A is a word in the language of any CFG has already been solved. Let us assume now that A is not a word generated by the CFG. In that case, we can con- vert the CFG to CNF, preserving the entire language. If there is a production of the form S-1 where is a terminal, then is a word in the language. If there are no such productions, we then propose the following algorithm: Step 1 For each nonterminal N that has some productions of the form N→ where is a terminal or string of terminals, we choose one of these productions and throw out all other productions for which N is on the left side. We then re- place N by r in all the productions in which N is on the right side, thus eliminat- ing the nonterminal N altogether. We may have changed the grammar so that it no longer accepts the same language. It may no longer be in CNF. That is fine with us. Every word that can be generated from the new grammar could have been generated by the old CFG. If the old CFG generated any words, then the new one does also. Step 2 Repeat step 1 until either it eliminates S or it eliminates no new nonterminals. If S has been eliminated, then the CFG produces some words; if not, then it does not. (This we need to prove.) The algorithm is clearly finite, because it cannot run step 1 more times than there are nonterminals in the original CNF version. The string of nonterminals that will eventually re- place S is a word that could have been derived from S if we retraced in reverse the exact se- quence of steps that lead from the terminals to S. If step 2 makes us stop while we still have not replaced S, then we can show that no words are generated by this CFG. If there were any words in the language, we could retrace the tree from any word and follow the path back to S. For example, if we have the derivation tree then we can trace backward as follows (the relevant productions can be read from the tree): B-b must be a production, so replace all B's with b's. Y→BB