CS 3350 Automata, Computability, and Formal Languages
Fall 2012 Final Exam

Name: __________________________________________________________

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:

0*U 01*
(Here, AB means concatenation of two languages A and B.)

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 transition is as follows: The state r0 is the only final state.

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: Use the general algorithm that we described in class (and that is described in the book) to list all the rules of the corresponding context-free grammar which are needed to deduce the sequence babb. Draw a parse tree explaining how this sequence is derived by using these rules.

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:

Trace it step-by-step on the example of a string "Oz".

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: Use the diagonalization algorithm that we described in class to generate the first three digits of a real number y that does not belong to this sequence.