Homework 1 Solutions

Problem #1

Induction on the length of y:

Base Cases:
At |y| = 0, y = epsilon, so the proof is just the definitions

delta-hat(q,epsilon) = q = f(q,epsilon).

By transitivity of equivalence,

delta-hat(q,epsilon) = f(q,epsilon)

At |y| = 1, y is a string consisting of the single arbitrary symbol a. With delta-hat we have a = epsilon.a, and thus

delta-hat(q,a) = delta-hat(q,epsilon.a) = delta(delta-hat(q,epsilon),a) = delta(q,a) (from basis 0)

And with f we have a = a.epsilon, and thus

f(q,a) = f(q,a.epsilon) = f(delta(q,a), epsilon) = delta(q,a)

We have delta-hat(q,a) = delta(q,a) = f(q,a). Again, by transitivity of equivalence, delta-hat(q,a) = f(q,a).

Induction:
We assume that delta-hat(q,w) = f(q,w) for any string w of length less than that of y. Now we can prove that delta-hat(q,y) = f(q,y) as follows:

y has at least two symbols (if it has less than two symbols, then it falls under our bases above). Let us represent y as axb, where a and b are two symbols of y, the first and last respectively, and x is an infix string, possibly empty, containing all other characters in y.

We have delta-hat(q,axb) = delta(delta-hat(q,ax),b) Because |ax| < |axb| = |y|, we can invoke the inductive hypothesis to get:

delta-hat(q,axb) = delta(f(q,ax),b) = delta(f(delta(q,a),x),b)

Again, because |x| < |axb| = |y|, we can substitute:

delta-hat(q,axb) = delta(delta-hat(delta(q,a),x),b) = delta-hat(delta(q, a),xb)

Finally, since |xb| < |axb| = y, we can conclude with:

delta-hat(q,axb) = f(delta(q,a),xb) = f(q,axb)

Since delta-hat(q,axb) = f(q,axb) and y = axb, we have delta-hat(q,y) = f(q,y), which is what we wanted to show. Because of the property of mathematical induction on the length of the string y, we can conclude that this property holds for all strings.

Problem #2

This is the 5-tuple definition for one such automaton, as well as the transition table; others are possible. Note the problem specifically asked for the 5-tuple notation of your automaton.

M = ({q0, q1, q2, q3, q4}, {0, 1}, delta, q0, {q0})

The transition function delta is described below:

State	On 0	On 1
q0	q0	q1
q1	q2	q3
q2	q4	q0
q3	q1	q2
q4	q3	q4

Problem #3

The DFA M = (Q x Sigma, {0,1}, delta, {p}, F) where delta is defined as:

	State	On 0	On 1
	{p}	{q,s}	{q}
*	{q}	{r}	{q,r}
	{r}	{s}	{p}
*	{s}	{}	{p}
*	{q,s}	{r}	{p,q,r}
*	{q,r}	{r,s}	{p,q,r}
*	{r,s}	{s}	{p}
*	{p,q,r}	{q,r,s}	{p,q,r}
*	{q,r,s}	{r,s}	{p,q,r}
	{}	{}	{}

The states in F are indicated with a "*" in the transition table.

4.

The solution to this problem is easiest shown graphically, but I will show it here as a transition diagram. There are simpler automata, but I will present the most straightforward one (which, incidentally, has 13 states and 15 arcs):

M = ({q_k|1 <= k <= 13}, {0,1}, delta, q0, {q12, q13})

delta =

State	On 0	On 1
q1	{q1,q2}	{q1,q3}
q2	{}	{q4}
q3	{q5}	{}
q4	{}	{q6}
q5	{q7}	{}
q6	{q6,q8}	{q6}
q7	{q7}	{q7,q9}
q8	{}	{q10}
q9	{q11}	{}
q10	{q12}	{}
q11	{}	{q13}
q12	{}	{}
q13	{}	{}