Week 11

Try to prove the DFSA we derived for binary strings that include the substring 011 last week.

P(x): = delta*(s, x)
= { q_0, if x is zero-free
= { q_1, if x has a 0 suffix but don't contain 011
= { q_2, if x has a 01 suffix but don't contain 011
= { q_3, if x contains 011.
Claim: if Sigma = { 0, 1}, then \forall string x, P(x).
Proof:
Base Case: For x = epsilon, delta*(q_0, epsilon) = q_0 since x is zero-free. All other cases follow since they all have a false antecedent. So P(x) is true in this case.
Induction Step: assume x' \in Sigma and P(x') is true. Let x = x'a, then x \in Sigma and either a = 0 or a = 1.
Case 1: a = 0. Then delta*(s, x) = delta*(q_0, x'a) = delta(delta*(q_0, x'), 0)

= { delta(q_0, 0), if x' is zero-free
= { delta(q_1, 0), if x' has a 0 suffix but don't contain 011
= { delta(q_2, 0), if x' has a 01 suffix but don't contain 011
= { delta(q_3, 0), if x' contains 011

= { q_1, if x has a 0 suffix but don't contain 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_1, if x has a 0 suffix but don't contain 011
= { q_3, if x contains 011.
So P(x) is true in Case 1.
Case 2: a = 1. Then delta*(s, x) = delta*(q_0, x'a) = delta(delta*(q_0, x'), 1)

= { delta(q_0, 1), if x' is zero-free
= { delta(q_1, 1), if x' has a 0 suffix but don't contain 011
= { delta(q_2, 1), if x' has a 01 suffix but don't contain 011
= { delta(q_3, 1), if x' contains 011

= { q_0, if x is zero-free
= { q_2, if x has a 01 suffix but don't contain 011
= { q_3, if x contains 011
= { q_3, if x contains 011.
So P(x) is true in Case 2.
Thus P(x) is true.
Therefore, if Sigma = {0, 1}, then \forall string x, P(x).