3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick87 Sep 30 '14 at 21:37
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.