## CS 3350 Automata, Computability, and Formal Languages Fall 2020, Test 3

Name: ____________________________

• you are allowed up to 5 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 out of time, just follow the few first steps of the corresponding algorithm.
Good luck!

1-2. Prove that the language L = {dnen+1fn+2} = {eff, deefff, ddeeeffff, ...} is not context-free.

3. Trace the following Turing machine on the example of the word yn: start, _ → work, R (here, _ means blank); work, y → R; work, n → y, R; work, _ → back, L; back, y → L; back, _ → halt. Explain how each step will be represented if we interpret the Turing machine as a finite automaton with two stacks.

4. Design a Turing machine that adds 10 (binary version of 2) to a binary number. Trace your Turing machine, step-by-step, on the example of the string 11. Why in Turing machines (and in most actual computers) the representation of a binary number starts with the least significant digit?

5. The following finite automaton describes strings with at least two letters y. This automaton has the starting state s, the state 1 meaning that we have letter y, the final state f, and the following transitions:

• from s, y leads to 1 and n leads to s;
• from 1, y leads to f and n leads to 1;
• from f, both y and n lead back to f.
Use the general algorithm to transform this finite automaton into a Turing machine. Show, step-by-step, how your Turing machine will accept the string yny.

6. Give the formal definition of a feasible algorithm. Give two examples different from what we had in class:

• an example of a computation time which is formally feasible, but not practically feasible, and
• an example of a computation time which is practically feasible but not formally feasible.

7. What is P? What is NP? What does it means for a problem to be NP-hard? NP-complete? Give brief definitions. Give an example of an NP-complete problem: explain what is the input, what is the desired output. Is P equal to NP?

8. Prove that the cubic root of 2 is not a rational number.

9. Formulate the halting problem. Prove that it is not possible to check whether a given program halts on given data.

10. Formulate Church-Turing thesis. Is it a mathematical theorem? Is it a statement about the physical world?