The following languages/problems are decidable: 1. The set of encodings of DFAs which do not accept any string containing an odd number of 1s. 2. The set of strings of the form R#S where R and S are regular expressions and L(R) is a subset of L(S). 3. The set of encodings where G is a context-free grammar with terminal alphabet {0,1} which generates some string over {1}. 4. The set of all Pascal programs P such that P does not halt in |P| steps, given an empty input file. The following languages/problems are undecidable: 1. The set of encodings where G is a context-free grammar with terminal alphabet {0,1} which generates all strings over {0,1}. Here is an outline of the proof. There exists a recursive function that, given any w, where is the encoding of a TM, produces an encoding of a context-free grammar, such that L(G) is the set of all strings which are not computations of M starting at w. If M does not halt with input w, then L(G) consists of all strings, because M has no computations starting at w. (Recall that a computation must end with a halting configuration.) If M halts with input w, then L(G) does not consist of all strings. Thus, if we could decide whether L(G) contains all strings, we could decide the halting problem. 2. The set of encodings where T is a Turing Machines with tape alphabet {0,1} which halt given input .