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:

This automaton accepts the word −01.

2. (For extra credit) Sketch a proof that the language {(n)2n, n = 1, 2, ...} = {()), (()))), ((()))))), ...} is not regular.