Fall 2012 Final Exam

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:

- the starting state s
_{0}, - the
state r
_{0}meaning that we have just read 0, - the
state r
_{1}meaning that we have just read 1.

- when we see 0, we move to
r
_{0}; - when we see 1, we move to
r
_{1}.

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 xy^{i}z 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:

- draw a tree that describes the derivation of the sequence bab,
- use this tree to determine the subdivision of this sequence into u, v, x, y, and z;
- for i
= 0 and i = 2, draw trees explaining how the corresponding
sequences uv
^{i}xy^{i}z can be derived in this grammar.

6 (8 points) The sequence babb is accepted by the following non-deterministic pushdown automaton:

- this automaton starts at state 0,
- when in state 0, the rule (b, ε) --> a leads to state 1,
- when in state 1, the rule (a, a) --> b leads to state 2,
- when in state 2, the rule (b, ε) --> t leads to state 2 again,
- when in state 2, the rule (ε, t) --> ε leads to state 3,
- when in state 3, the rule (b, b) --> ε leads to the state 1, which is a final state.

7 (8 points). Let N

8 (16 points).

8a. Design a Turing machine for making a given word plural:

- if the given word ends in s or in z, we add "es"
- in all other cases, we add "s".

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:

- x
_{1}= 0.0666... - x
_{2}= 0.1300... - x
_{3}= 0.2012... - ...