1 (5 points) Prove that the square root of 5 is irrational.
2a. Use a general algorithm to design a non-deterministic finite automaton recognizing the language (0 U 1*)0.
2b. Use the general algorithm to design a deterministic finite automaton recognizing this same language.
3a. Use a general algorithm to transform the following finite automaton (for checking whether a given binary number is odd) into the corresponding regular expression. This automaton recognizes unsigned binary integers. This automaton has three states:
3b. On the example of this automaton, explain, in detail, how the sequence 0101 will be presented as xyz according to the pumping lemma. For this sequence, check -- by tracing step-by-step -- that the sequence xyiz for i = 2 is indeed accepted by the automaton.
3c. Use a general algorithm to describe a context-free grammar corresponding to this finite automaton.
3d. On the example of this grammar, explain, in detail, how the sequence 0101 will be presented as uvxyz according to the pumping lemma for context-free grammars. For this sequence, check -- by tracing step-by-step -- that the sequence uvixyiz for i = 2 is indeed derived by this grammar.
3e. Use the general algorithm to transform this grammar into Chomsky normal form.
3f. Use the general algorithm to describe a non-deterministic pushdown automaton that corresponds to this grammar.
5a. Describe a Turing machine that replaces all 0s with 1s and all 1s with 0s. Illustrate, step-by-step, how this Turing machine works, on the example of input 10, the result should be 01. For the first two intermediate states, show how the state of the Turing machine can be represented by a finite automaton with two stacks.
5b. Formulate Church-Turing thesis about Turing machines. Is it a mathematical theorem? Is it a statement about the physical world?
6a. What is the current definition of a feasible algorithm. Give two examples explaining why this definition does not fully capture the commonsense meaning of feasible.
6b. Give a precise definition of a problem from the class NP.
6c. Explain what it means for a problem to be NP-hard.
6d. Give an example of an NP-hard problem.
6e. Can every NP-hard problem be solved by a feasible algorithm?
7a. Let us assume that we have the following sequence of functions: f0(n) = 0, f1(n) = n, f2(n) is nowhere defined, f3(n) = n2, etc. Write down the first 4 values f(0), f(1), f(2), and f(3) of the following diagonal function:
7b. This diagonal construction is used to prove that there is a problem for which no general algorithm is possible. What is this problem?
7c. For extra credit: how is the diagonal construction used in this proof?