CS 3350 Automata, Computability, and Formal Languages
Fall 2012 Quizzes

1. Prove that the language {anb2n: 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 transition is as follows: 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 xy2z 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.