CS 3350
Automata, Computability, and Formal Languages
Fall 2018, Quiz
2
Last 4 digits of your UTEP ID number:
____________________________
1. In class, we had the following finite automaton for recognizing
signed or unsigned binary integers. This automaton has 5 states:
the starting state start (st), the state sign_read (sr), the state
signed_integer (si), the state unsigned_integer (u), and the sink
(error) state e. This automaton has two final states: si and u.
The transitions are as follows:
 from st, + or −
lead to sr, 0 or 1 lead to u, every other symbol leads to e;

from sr, 0 or 1 lead to si, any other symbol leads to e;
 from
si, 0 or 1 lead to si, any other symbol leads to e;
 from u, 0
or 1 lead to u, any other symbol leads to e;
 from e, any
symbol leads to e.
This automaton accepts the word −01.
 Trace, stepbystep, that this word is indeed accepted by
the given automaton.
 Use this tracing to find the parts x, y,
and z of this word corresponding to the Pumping Lemma.
 Trace
that the words xyyz and xyyyz are also accepted by this
automaton.
2. (For extra credit) Sketch a proof that the language
{(^{n})^{2n}, n = 1, 2, ...} = {()), (()))),
((()))))), ...} is not regular.