1 (8 points). Prove that the square root of 6 is irrational.
2 (16 points).
2a. Use a general algorithm to design a non-deterministic finite automaton recognizing the following language:
2b. Apply the general algorithm to transform the non-deterministic finite automaton from Part 2a a deterministic finite automaton recognizing this same language.
3 (16 points).
3a. Use a general algorithm to transform the following finite automaton (for checking whether a given binary number is even) into the corresponding regular expression. This automaton recognizes signed binary integers. The alphabet for this automaton consists of symbols 0, and 1. The automaton has three states:
3b. On the example of this automaton, explain, in detail, how the following sequences will be presented as xyz according to the pumping lemma: 00 and 110. For each of these sequences, check -- by tracing step-by-step -- that the sequences xyiz for i = 2 are indeed accepted by the automaton.
4 (8 points). Use Pumping Lemma to prove that the language L consisting of all the words that have at least three times as many b's as a's is not regular. This language includes an empty string ε, strings abbb, bbba, babbb, bbbaabbbb, etc.
5 (24 points).
5a. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form: S --> AA, A --> BaB, B --> AbA, A --> ε, B --> ε.
5b. Use the general algorithm to design a pushdown automaton that recognizes exactly the above context-free language.
5c. For the above context-free grammar:
6 (8 points) The sequence babb is accepted by the following non-deterministic pushdown automaton:
7 (8 points). Let Na(s) denote the number of a's in a string s, Nb(s) denote the number of b's, and Nc(s) denote the number of c's. Prove that the language consisting of all the words s for which Na(s) >= 3 * Nb(s) and Na(s) >= 3 * Nc(s) (i.e., words which have exactly at least three times as many a's as b's or c's) cannot be recognized by a pushdown automaton.
8 (16 points).
8a. Design a Turing machine for making a given word plural:
8b. Formula Church-Turing thesis. It is a mathematical theorem? Can it be proven? Is it a statement about the physical world?
9 (8 points). Let us assume that we have the following sequence of real numbers: