## 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:

• is divisible by 3 (state s0),
• has remainder 1 when divided by 3 (state s1), and
• has remainder 2 when divided by 3 (state s2).
The state s0 is the starting state, states s1 and s2 are final states. When the automaton sees the symbol a, it goes:
• from state s0 to state s1;
• from state s1 to state s2; and
• from state s2 to state s0.

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:

• the starting state s
• the final state f, and
• the error state e.
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:

• draw a tree that describes the derivation of the sequence aaabbb,
• 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 uvixyiz can be derived in this grammar.

9. The sequence abcabc is accepted by the following pushdown automaton:

• this automaton starts at state 0,
• when in state 0, the rule (a, ε) --> a leads to state 1,
• when in state 1, the rule (b, a) --> b leads to state 2,
• when in state 2, the rule (c, ε) --> c leads to state 2 again,
• when in state 2, the rule (a, c) --> ε leads to state 3,
• when in state 3, the rule (b, b) --> ε leads to state 2, and
• finally, when in state 2, the rule (c, ε) --> ε leads us to the final state 0.
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:

• x0 = 0.16666...
• x1 = 3.25000...
• x2 = 1.12345...
• x3 = 0.14141...
• x4 = 0.01250...
• ...
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:

• first, we list all the pairs (a, b) whose sum a + b is equal to 0,
• then, we list all the pairs (a, b) whose sum a + b is equal to 1,
• then, we list all the pairs (a, b) whose sum a + b is equal to 2,
• ...
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:
• which is pair # 0,
• which is pair # 1,
• ...,
• which is pair # 14.