Fall 2018, Final Exam

General comments:

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

1. *Finite automata and regular languages:*
2. *Beyond finite automata: pushdown automata and context-free
grammars:*
3. *Beyond pushdown automata: Turing machines*
4. *Beyond Turing machines: computability*

1a. Design a finite automaton for recognizing binary sequences that have odd number of 0s and odd number of 1s. Assume that the input strings contain only symbols 0 and 1. The easiest is to have 4 states:

- the desired (final) state oo in which we have odd number of 0s and odd number of 1s,
- the state eo, in which we have even number of 0s and odd number of 1s, and
- similarly defined states oe (odd-even) and ee (even-even).

1b. On the example of this automaton, show how the word 1000 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. (If you are running out of time, it is Ok not to finish, just eliminate the first state.)

1d-e. Some of the words from the corresponding language (but not
all of them) The resulting language can be described by a regular
expression 1^{*}(00)^{*}. Use a general
algorithm to transform this regular expression into a finite
automaton: first a non-deterministic one, then a deterministic
one.

2a. A team is above average if in the championship, it has more wins (W) than losses (L). For example, a team with a record WLW is above average. Prove that the language consisting of all sequences of W and L that make the team above average 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 1000.

2c. For the context-free grammar from the Problem 2b, show how the word 1000 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 1000.

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

- how the compiler will transform a Java expression 8 / 4 / 2 into inverse Polish notation, and
- how it will compute the value of this expression.

3a. To celebrate Cinco de Mayo, students decided to decorate the walls a classroom in green (G), white (W), and red (R), colors of the Mexican flag. To get a good image, they want to make sure that there are exactly the same number of segments of each color. So, if the walls are decorated in GGWRWR, it is good, but if it is GGWRR, it is not good. Prove that the set of all "good" color combinations is not context-free and therefore, cannot be recognized by a pushdown automaton.

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 1000. Describe, for each step, how the state of the tape can be represented in terms of states of two stacks.

3d-e. Design Turing machines for computing a − 1 in unary and in binary codes. Trace both for a = 3, i.e., for a = 111 in unary code and a = 11 in binary code.

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. Not all algorithms are feasible, but, unfortunately, we do not have a perfect definition is feasibility. Give a current formal definition of feasibility and give two examples:

- an example of an algorithm's running time which is feasible according to the current definition but not practically feasible, and
- an example of an algorithm's running time which is practically feasible but not feasible according to the current definition.

4d. Briefly describe what is P, what is NP, what is NP-hard, and what is NP-complete. Is P equal to NP?

4e. Give an example of an NP-complete problem: what is given, and what we want to find.

4f. Give definitions of a recursive (decidable) language and of a recursively enumerable (Turing-recognizable) language.