CS 3350 Automata, Computability, and Formal Languages
Fall 2015, Final Exam, 3-4:20 pm version

Name: __________________________________________________________

General comments:

Good luck!

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)

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 q0 meaning that we have only read 0s so far, and
  • the state q1 meaning that we have read at least one 1, and thus, the number is positive.
The state q1 is the only final state. The transition is as follows:
  • when we see 1 in any state, we move to q1,
  • when we see 0 in the state s or in the state q0, we move to q0,
  • when we see 0 in the state q1, we remain in 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 anbncnan, 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: f0(n) = 1, f1(n) = 2n, f2(n) is nowhere defined, f3(n) = n3, 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?