############## The following hints are only intended as either hints or as a quick check that you are on the right track. The answers do not correspond to actual exam answers. ############## 1a: not the same. 1b: the same. (It's important to know the difference between the empty string and the empty set.) 1c: not the same, 1d: not the same. For the expressions that are not equivalent one need to come up with concrete counter examples. 2b State 0 1 {q0,q1,q2} {q2,q3} {q2,q3} {q2,q3} {} {q2,q3,q4} {q2,q3,q4} {} {q2,q3,q4} {} {} {} For a full score one either needs to explicitly include the trash state {} or clarify that it has been omitted. 3a: no, every finite language is regular, but clearly there exist infinite languages that are regular. 3b: yes, can be recognized by a very simple regular expression. 3c: yes, since every regular language trivially is context-free. 3d: yes, by mapping everything to the empty string. This preserves string concatenation. [More detailed explanations than this are expected in actual answers] 4a: the marking algorithm will not collapse any states. However, note that the state F is inaccessible. Thus, it should be removed in pre-processing step (this was discussed at the lecture and is strongly hinted in the lecture notes). However, a solution which correctly applies the marking algorithm without removing the inaccessible state will be given almost full credit. 4b: the point of this relation is to relate states together if they are equivalent with respect to accept/reject. Which states are equivalent under this notion? 5a: a simple string to use as a starting point is 0^p 1^p. Then the argument is more or less the same as the go-to example {0^n 1^n | n >= 1} (see lecture notes). 5b: one can e.g. consider the equivalence classes [0], [00], ... An actual argument is required: it's not sufficient to just state that these strings induce different equivalence classes. 6: this language is context-free, see, e.g., https://cs.stackexchange.com/questions/2127/context-free-grammar-for-an-bm-anm. 7: to answer this question one needs to remember the distinction between Turing-decidable (the machine never loops) and Turing-recognizable (the machine might loop for strings outside the language). The answer to a) is yes (what does this machine look like?) and the answer to b) is no (try to come up with concrete examples, a good strategy is to consider languages that are Turing-recognizable but not Turing-decidable, see the lecture notes). Clear (but high-level) constructions which explains the languages and Turing machines in question are required to get credits.