Fall 2012 Homeworks

2. Use a general algorithm to design a non-deterministic finite automaton recognizing the following 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: s_{0}, s_{1}, and s_{2},
corresponding to the cases when the number of a's read so far:

- is divisible by 3 (state s
_{0}), - has remainder 1 when divided by 3 (state s
_{1}), and - has remainder 2 when divided by 3 (state s
_{2}).

- from state s
_{0}to state s_{1}; - from state s
_{1}to state s_{2}; and - from state s
_{2}to state s_{0}.

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.

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

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

11. Let us assume that we have the following sequence of real numbers:

- x
_{0}= 0.16666... - x
_{1}= 3.25000... - x
_{2}= 1.12345... - x
_{3}= 0.14141... - x
_{4}= 0.01250... - ...

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,
- ...

- which is pair # 0,
- which is pair # 1,
- ...,
- which is pair # 14.