C S 341 Final: CS 341 FinalPracticeOnWeb
Document Summary
If you are trying to prove something and you know that you haven"t got it right, say so. You can do this part by writing an appropriate grammar (or regular expression), exhibiting an appropriate recognizing machine, using closure properties, or by showing that the language is finite. What i mean by exhibit a recognizing machine is: for an fsm: draw it, for a pda: draw it, but if it is very complicated, also provide a description of how it works. We will give partial credit for the description even if the details of the machine are missing or wrong: for a turing machine: describe an algorithm in clear english. Any clear algorithm is acceptable. (8 points) prove that the language is not in the next most restricted category, except as noted below, in which case these points will be assigned to part ii. H = { : tm m halts on input string w}