CS 3350 Automata, Computability, and Formal Languages
Fall 2012 Homeworks

1. Prove that square root of 3 is irrational.

2. Use a general algorithm to design a non-deterministic finite automaton recognizing the following language:

1(0 U 1)*
(Here, AB means concatenation of two languages A and B.) After that, use the general algorithm to design a deterministic finite automaton recognizing this same language.

3. Use a general algorithm to transform the following finite automaton (for checking non-divisibility by 3) into the corresponding regular expression. The alphabet for this automaton consists of a single symbol a. The automaton has 3 states: s0, s1, and s2, corresponding to the cases when the number of a's read so far:

The state s0 is the starting state, states s1 and s2 are final states. When the automaton sees the symbol a, it goes:

4. Use a general algorithm to transform the following finite automaton into the corresponding regular expression. The alphabet for this automaton consists of letters a, b, and c; a word is accepted by this automaton if it has an odd number of letters a and no letters c. The automaton has three states:

In the state s, the symbol a leads to f, symbol b leads to s, and symbol c leads to e. In the state f, symbol a leads to s, symbol b leads to f, and symbol c leads to e. In the state e, all three symbols lead to e.

5. On the example of the automaton from Problem 4, explain, in detail, how the following sequences will be presented as xyz according to the pumping lemma: abaa, bab, bbba. For each of these sequences, check -- by tracing step-by-step -- that the sequences xyiz for i = 2 are indeed accepted by the automaton.

6. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form: S --> A, S --> B, A --> aBb, B --> aAb, A --> ε, B --> ε.

7. Use the general algorithm to design a pushdown automaton that recognizes exactly the context-free language described in Problem 6.

8. For the context-free grammar described in Problem 6:

9. The sequence abcabc is accepted by the following 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 abcabc. Draw a parse tree explaining how this sequence is derived by using these rules.

10. Prove that the language {anb2nc3n, n = 0, 1, 2, ...} cannot be recognized by a pushdown automaton.

11. 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 five digits of a real number y that does not belong to this sequence.

12. Let us assume that we list all possible pairs of natural numbers as follows:

Among pairs (a, b) with a fixed sum, we list them in the increasing order of a; e.g., (3, 4) goes before (5, 2). Describe the first 15 pairs in this listing: