Fall 2015, Final Exam, 3-4:20 pm version

General comments:

- you are allowed up to 10 pages of handwritten notes;
- if you need extra pages, place your name on each extra page;
- the main goal of most questions is to show that you know the corresponding algorithms; so, if you are running of time, just follow the few first steps of the corresponding algorithm;
- each question will be graded on its own merit; so, for example, if on one stage, you got a wrong context-free grammar, but on the second stage, you correctly apply the Chomsky normal form algorithm to the resulting grammar, you will get full credit for the second stage.

1 (5 points) Prove that the square root of 7 is irrational.

2 (15 points)

2a. Use a general algorithm to design a non-deterministic finite
automaton recognizing the language
(1 U 0^{*})1.

2b. Use the general algorithm to design a deterministic finite automaton recognizing this same language.

3 (30 points)_{1} is the only final state. The transition is
as follows:

3a. Use a general algorithm to transform the following finite automaton (for checking whether a given binary number is greater than 0) into the corresponding regular expression. This automaton recognizes unsigned binary integers. This automaton has three states:

- the starting state s,
- the state q
_{0}meaning that we have only read 0s so far, and - the state q
_{1}meaning that we have read at least one 1, and thus, the number is positive.

- when we see 1 in any state, we move to q
_{1}, - when we see 0 in the state s or in the state q
_{0}, we move to q_{0}, - when we see 0 in the state q
_{1}, we remain in q_{1}.

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 xy^{i}z 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 uv^{i}xy^{i}z 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.

4 (10 points) Use the Pumping Lemma for context-free languages to prove that
the
language L consisting of all the words of the type
a^{n}b^{n}c^{n}a^{n}, n = 0, 1, 2, ...,
is not context-free.

5 (10 points)

5a. Describe a Turing machine that replaces all binary digits with 1s. Illustrate, step-by-step, how this Turing machine works, on the example of input 10, the result should be 11. 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?

6 (25 points)

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?

7 (10 points)

7a. Let us assume that we have the following sequence of
functions: f_{0}(n) = 1, f_{1}(n) = 2n, f_{2}(n)
is nowhere defined, f_{3}(n) = n^{3}, etc. Write down
the first 4 values f(0), f(1), f(2), and f(3) of the following diagonal function:

- f(n) =
f
_{n}(n) + 1 if the function fn is applicable to n and - f(n) = 0 otherwise.

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?