Base Cases:
At |y| = 0, y = epsilon, so the proof is just the definitions
By transitivity of equivalence,
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.
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 |
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.
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 | {} | {} |