## 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, step-by-step, 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.