# Using induction to prove transition states are the same

Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$.

Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$.

Show that for any non-empty word $w$ over $\Sigma$, we have $\delta^{*}\left(s_0,w\right)=\delta^{*}\left(s_f,w\right)$.

I know there is something I am overlooking, specifically with regards to the non-empty word. Here is my attempt at an answer via a proof by induction:

Let's use a word $w=ax$

$$\delta^{*}\left(s_f,ax\right)=\delta\left(\delta^{*}\left(s_f,a\right),x\right)$$

Since $\delta^{*}\left(s_0,w\right)=\delta^{*}\left(s_f,w\right)$.

We can also write this equation as $$\delta^{*}\left(s_f,ax\right)=\delta\left(\delta^{*}\left(s_f,a\right),x\right) = \delta\left(\delta^{*}\left(s_0,a\right),x\right)=\delta^{*}\left(s_0,ax\right)\,.$$

This seems almost too obvious... I am new to this style of maths and would appreciate some guidance with regards to my proof style and if I'm ommitting something significant.

New attempt thanks to @Patrick87's guidance:

$$\delta^{*}\left(s_f,ax\right)=\delta^{*}\left(\delta\left(s_f,a\right),x\right) = \delta^{*}\left(\delta\left(s_0,a\right),x\right)=\delta^{*}\left(s_0,ax\right)\,.$$

I think this makes sense but I can't help but feel something is missing.

• Very close, but I think you've mixed up some $\delta$ with $\delta^*$. You should have $\delta^*(s_f, ax) = \delta^*(\delta(s_f, a), x)$ for the first one. Think about it; $\delta$ takes a single symbol as the second argument, and $\delta^*$ takes a string. Also, we supposed only that $\delta(s_0, a) = \delta(s_f, a)$, not anything about $\delta^*$. Otherwise, I think you've got the right idea. – Patrick87 Sep 30 '14 at 21:37

We use induction on the length of $w$. Let this length be denoted by $|w|$

Base case: $|w|$ = 1

Immediate by the assumption that $\forall a∈Σ. δ(s_0,a)=δ(s_f,a)$

Induction hypothesis: $δ^*(s_0,w)=δ^*(s_f,w)$ for $|w| = k$ where $k \geq 1$

Inductive step: Assuming the induction hypothesis, prove that it works for $k+1$:

Let $w$ be a word s.t $|w| = k+1$. Clearly $w$ can be seen as two strings $w = w^{-1} \circ v$ where $\circ$ is concatenation of strings.

As $|w^{-1}| = k$ we, by induction, get that $δ^*(s_0,w^{-1})=δ^*(s_f,w^{-1})$. As $x$ is a string of length $1$ we get by $\forall a∈Σ. δ(s_0,a)=δ(s_f,a)$ that $δ^*(s_0,w)=δ^*(s_f,w)$

The proof could be a bit more formal, but atleast the intuition should be clear.