[Math] Proving Language accepted by DFA

automata

I am stuck with a problem, as my proving skills aren't good(trying to improve).
Prob:
Given a State Table of DFA, decribe what language is accepted, and prove by induction it accepts that language, use induction on length of string.

              | 0  1 
          ->A | B  A
            B | C  A
           *C | C  C

As it accepts language, stings with at least one 00 in them.
Basis: let w be the string, s.t w = 00
dlt-hat(A,w) = C as C is accepting state

What would be Inductive Hypothesis, i know there will be cases like
w = za, where z could be sting with not containing 00, or containg last symbol as 0 and a could be 0 or 1.

@copper.hat,
Let w = x00y such that x cannot contain 00 and it ends with 1 and y can be any things {0,1}*
Basis: For basis clause let x and y be empty (e)
1: del-hat(A,e) = A
2: del-hat(A,00) = C
3: del-hat(C, e) = C
Induction:
1) Let x=z1 and Inductive hypothesis(IH) be del-hat(A,z) = A.
del-hat(A,x) = del-hat(A,z1) = del-hat(del-hat(A,z),1) = del-hat(A,1) {from IH}
And del-hat(A,1)=A.
2) del-hat(A,00) = A, as basis clause.
3) let y = za where a can be {0,1}* and Inductive hypothesis be del-hat(C,z) = C
del-hat(C,za) = del-hat(del-hat(C,z),a) = del-hat(C,a) [from IH] which is C.
Hence all three cases have been shown.

Best Answer

Perhaps you can extract a clear inductive proof from the following:

Let $\Sigma = \{0,1\}$.

You need to prove $\hat{\delta}(A, w) = C$ iff $w$ has the form $w=w_1 00 w_2$, where $w_1,w_2 \in \Sigma^*$.

($\Rightarrow$): Suppose $\hat{\delta}(A, w) = C$. Let $w = \alpha_1 \cdots \alpha_n$ with $\alpha_k \in \Sigma$, $\sigma_1 = A$ and $\sigma_{k+1} = \delta(\sigma_k, \alpha_k)$. Let $i$ be the first time that $\sigma_i = C$. Then we must have $\sigma_{i-1} = B$, $\alpha_{i-1} = 0$, $\sigma_{i-2} = A$ and $\alpha_{i-2} = 0$. If we let $w_1 = \alpha_1 \cdots \alpha_{i-3}$, $w_2 = \alpha_{i} \cdots \alpha_{n}$, then $w = w_1 00 w_2$.

($\Leftarrow$): Suppose $w=w_1 00 w_2$. Let $\sigma = \hat{\delta}(A, w_1)$. If $\sigma = C$ we are finished, as $\delta(C, \alpha) = C$ for all $\alpha \in \Sigma$. If $\sigma = B$, then $\hat{\delta}(A, w_1 0) = \delta(B, 0) = C$, and we are finished. Finally, If $\sigma = A$, then $\hat{\delta}(A, w_1 0) = B$ and $\delta(B, 0) = C$, hence $\hat{\delta}(A, w_1 00) = C$ which finishes the proof (since $\hat{\delta}(C, w_2) = C$).

Related Question