General comments:
1a. Design a finite automaton for recognizing binary sequences that have exactly two zeros. Assume that the input strings contain only symbols 0 and 1. The easiest is to have 4 states: no-zeros, 1-zero, 2-zeros, and more-than-2-zeros, 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 01101.
1b. On the example of this automaton, show how the word 01101 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. The resulting language can also be described by a regular expression 1^{*}01^{*}01^{*}. Use a general algorithm to transform this regular expression into a finite automaton: first a non-deterministic one, then a deterministic one.
2a. Prove that the language consisting of all expressions that contain twice as many a's as b's 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 01101.
2c. For the context-free grammar from the Problem 2b, show how the word 01101 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 01101.
2f. Use the general stack-based algorithms to show:
3a. Prove that there exists a language that is not context-free and therefore, cannot be recognized by a pushdown automaton. You can use the same language we had in class or -- for extra credit -- some other language.
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 01101. 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 + 2 in binary code. Trace it for the binary number n = 10_{2} (which is 2 decimal); the result of the computation should 2 + 2 = 4_{10}, i.e., 100_{2.}
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:
4d. Not all algorithms are feasible, but, unfortunately, we do not have a perfect definition is feasibility. Give two examples:
4e. Briefly describe what is P, what is NP, and what is NP-hard.