## CS 3350
Automata, Computability, and Formal Languages

Fall 2012
Quizzes

1. Prove that the language {a^{n}b^{2n}: n ≥
0} is not regular.
2. The following automaton recognizes signed or unsigned binary
integers; signs themselves are also allowed; they mean 0. The
alphabet for this automaton consists of symbols −, +, 0,
1, ..., 9. The automaton has four states:

- the
starting state s
_{0}, - the state s meaning a signed
integer,
- the state u meaning an unsigned integer,
- the
error state e.

The transition is as follows: - In
s
_{0}, signs − and + lead to s, while a digit
lead to u. - In s, a digit lead back to s, while − or
+ lead to e.
- In u, a digit lead back to u, while −
or + lead to e.
- e is a sink state: once we are in e, we
stay in e no matter what symbol is read.

The states s and
u are the final states. On the example of this automaton,
explain, in detail, how the sequence −13 will be
presented as xyz according to the pumping lemma. Check -- by
tracing step-by-step -- that the sequence xy^{2}z is
indeed accepted by the automaton.
3. Design a Turing machine for eliminating the last symbol of
the string (or doing nothing is the string is already empty),
and trace it step-by-step on the example of a 3-character
string BOO.