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 transition is as follows: 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 xyiz 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.