## CS 3350
Automata, Computability, and Formal Languages

Fall 2012
Test 1

Name: __________________________________________________________
1. Prove that the cubic root of 2 is irrational.

2. Use a general algorithm to design a non-deterministic finite
automaton recognizing the following language:
1^{*}(0 U 1) (Here, AB means concatenation of
two languages A and B.) After that, use the general algorithm
to design a deterministic finite automaton recognizing this
same language.

3. Use a general algorithm to transform the following finite
automaton into the corresponding regular expression. This automaton
recognizes signed binary integers. The
alphabet for this automaton consists of symbols −, +, 0, and 1.
The automaton
has four states:
- the starting state s
_{0},
- the state s meaning that a sign has been read,
- the state d meaning that a digit has been read,
- the error state e.

The transition is as follows:
- In s
_{0}, signs − and + lead to s, while 0 or 1 lead to e.
- In s, 0 or 1 lead to d, while − or + lead to e.
- In d, 0 or 1 lead back to d, 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 state d is the only final state.

4. On the example of the automaton from Problem 3, explain, in detail,
how the following sequences will be presented as xyz according to the
pumping lemma: +001 and −100. For each of these sequences, check -- by tracing
step-by-step -- that
the sequences xy^{i}z for i = 2 are indeed accepted by the
automaton.

5. Use the Pumping Lemma to prove that the language L consisting of
all the words that have twice as many b's as a's is not regular.
This language includes an empty string ε, strings abb, bab,
bba, aabbbb, ababbb, etc.