## CS 3350 Automata, Computability, and Formal Languages Fall 2015, Final Exam, 12-1:20 pm version

Name: __________________________________________________________

• 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.
Good luck!

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

2 (15 points)

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.

3 (30 points)

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:

• the starting state s,
• the state q0 meaning that we have just read 0, and
• the state q1 meaning that we have just read 1.
The state q1 is the only final state. The transition is as follows:
• when we see 0, we move to q0,
• when we see 1, we move to q1.

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.

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 xnynzntn, n = 0, 1, 2, ..., is not context-free.

5 (10 points)

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?

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

• f(n) = fn(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?