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:
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:
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.