CS 3350 Automata, Computability, and Formal Languages
Spring 2020, Final Exam

Name: __________________________________________________________

General comments:

Good luck!

1. Finite automata and regular languages:

1a. Design a finite automaton for recognizing binary sequences that end with 1. Assume that the input strings contain only symbols 0 and 1. The easiest is to have two states:

You just need to describe transitions between these states, and which states are final. Show, step-by-step, how your automaton will accept the string 011 (that corresponds to binary number 110).

1b. Explain why in most computers binary numbers are represented starting with the lowest possible digit.

1c. On the example of the above automaton, show how the word 011 can be represented as xyz in accordance with the pumping lemma.

1d. 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.)

1e-f. The resulting language can be described by a regular expression (0 U 1)*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. In a fictitious state of Saxet, four universities A, B, C, and D -- located in four different cities -- compete for state funding. They want to make sure that each got an equal number of funds. So, e.g., if we the sequence of allocated grants is ABABCCDD, this is good. Prove that the set of all "good" sequences is not regular and therefore, cannot be recognized by a finite automaton.

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

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

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

3. Beyond pushdown automata: Turing machines

3a. In a fictitious state of Saxet, four universities A, B, C, and D -- located in four different cities -- compete for state funding. They want to make sure that each got an equal number of funds. So, e.g., if we the sequence of allocated grants is ABABCCDD, this is good. Prove that the set of all "good" sequences 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 011. 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 − 2 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.

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

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.