## CS 3350 Automata, Computability, and Formal Languages Spring 2016, Final Exam

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. Finite automata and regular languages:

1a. Design a finite automaton for recognizing unsigned binary integers. Assume that the input strings contain only symbols 0 and 1. The easiest is to have exactly 3 states: start, accept, and reject, you just need to describe transitions between these states. Show, step-by-step, how your automaton will accept the string 01011.

1b. On the example of this automaton, show how the word 01011 can be represented as xyz in accordance with the pumping lemma.

1c. Use a general algorithm to describe a regular expression corresponding to the finite automaton from the Problem 1a.

1d-e. Unsigned integers can also be described by a regular expression (0 U 1)(0 U 1)*. Use a general algorithm to transform this regular expression into a finite automaton: first a non-deterministic one, then a deterministic one.

2. Beyond finite automata: pushdown automata and context-free grammars:

2a. Prove that the language consisting of all expressions that contain equal number of opening and closing parentheses is not regular.

2b. Use a general algorithm to transform the finite automaton from the Problem 1a into a context-free grammar (CFG). Show, step-by-step, how this CFG will generate the word 01011.

2c. For the context-free grammar from the Problem 2b, show how the word 01011 can be represented as uvxyz in accordance with the pumping lemma.

2d. Use a general algorithm to translate the CFG from 2b into Chomsky normal form.

2e. Use a general algorithm to translate the CFG from 2b into an appropriate push-down automaton. Explain, step-by-step, how this automaton will accept the word 01011.

2f. Use the general stack-based algorithms to show:

• how the compiler will transform the expression (2 + 3) * (1 − 2) into inverse Polish notation, and
• how it will compute the value of this expression.

3. Beyond pushdown automata: Turing machines

3a. One of the ways to describe a conditional statement in Java is to use an expression (...) ... : ..., with two parentheses and a colon. For example, the following Java program computes the absolute value of x:
(x > 0) x : − x;
Prove that the language consisting of all expressions that contain the same number of opening parentheses, closing parentheses, and colons is not context-free.

3b-c. Use a general algorithm to design a Turing machine that accepts exactly all sequences accepted by a finite automaton from Problem 1a. Show, step-by-step, how this Turing machine will accept the word 01011. Describe, for each step, how the state of the tape can be represented in terms of states of two stacks.

3d. Design a Turing machine for computing n + 1 in unary code. Trace it for n = 1.

4. Beyond Turing machines: computability

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

4b. Prove that the halting problem is not algorithmically solvable.

4c. In the proof that the halting problem is not algorithmically solvable, we use a diagonal function f(n) which was defined as follows:

• f(n) = jn(n) + 1 if n is a valid code of a Java program and jn halts on n;
• f(n) =0 otherwise.
Write down the first 3 values f(0), f(1), and f(2) of the diagonal function f(n) for the following case:
• j0(n) = 3;
• 1 is not a valid numerical code of a program; and
• j2(n) = 2 * n.

4d. Not all algorithms are feasible, but, unfortunately, we do not have a perfect definition is feasibility. Give two examples:

• an example of an algorithm which is feasible according to the current definition but not practically feasible, and
• an example of an algorithm which is practically feasible but not feasible according to the current definition.

4e. Briefly describe what is P, what is NP, and what is NP-hard.