Assignment I

Due date Sep. 17, 2003

1. Prove that the sum of the cubes of the integers from 1 to N is

N^2 (N+1)^2 / 4,

where "^" denotes exponentiation.

2. Give the DFA accepting the following language over the alphabet {0, 1}: the set of strings that include 011 as a substring.

3. Same question, for the language that consists of strings that interpreted as integers, denote a value that is a multiple of five. For example, 101, 1010, 1111, 11110, etc, are in the language, but 110 is not.

4. Suppose we have an automaton A with alphabet S, start state q0, a single accepting state qf, and a transition function d that is such that for all symbols a in S, d (q0, a) = d (qf, a). Let L (A) be the language recognized by A. Show that if x is a nonempty string in L(A), then xx, xxx, ... x^k (x repeated k times) is also in L (A).

5. Describe a non-determininistic automaton that accepts the language over the alphabet {0,1..9} (the decimal digits) whose strings are such that the final digit has appeared before at some position in the string.