## 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 s0,
• 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 s0, 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 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.