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

Name: ____________________________

General comments:

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:

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:

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?