```
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 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)

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