Typical mistakes on Automata Test 3 Problem 3-4: you should show how the word baba is generated by the resulting Chomsky form grammar, not by the original grammar Problem 6: you should select the lowest pair of repeating variables on the same branch, some students selected a pair which is not on the same branch Problem 7: some of you started right, but never explained what is the contradiction; some used the wrong pumping lemma and thus proved that the language is not regular - which is not what this problem asks Problem 8: " Unary numbers consists of 1s only, 3 in unary is 111 " Designing a Turing machine means describing its rules " Your Turing machine should work for all n, not just for n = 0 " Your Turing machine should be deterministic: you cannot have two different rules for the same pair (state, symbol) " Please trace your Turing machine correctly, every transition to the next state should follow one of your rules Problem 10: there are two types of Turing machines " Some Turing machines perform computations. These machines stop when they reach a special state "halt". If we are computing a function f(n), this means that when we start with a Turing machine on which n is written, we should end up with a Turing machine on which f(n) is written. For these Turing machines it is important to rewind, this way it is easy to implement a composition f(g(n)) of two functions if we have Turing machines for computing f(n) and g(n). " Other Turing machines accept or reject a word. In this case, the Turing machine stops if it reaches one of the two stopping states: accept-state or reject-state. For these Turing machines, this acceptance or rejection is the main objective, so what is on the tape by the time this machine stops does not matter - and also, since no composition is possible here, in the definition that we had in class, we do not need to rewind: once you reach the accept- or reject-state, you just stop. For these machines, there is no additional halt state - as seen in the programming homework that you had.