# A question about the language of a non-deterministic FSA defined by a non-deterministic FSA with epsilon moves

I have tried to solve the following problem and my claims were marked as wrong, I would appreciate it if someone could point out my mistake

Let $A=(Q,\Sigma,q_{o},\delta,F)$ be a finite state automata with epsilon moves s.t $\delta(q_{0},\epsilon)=\emptyset$. Define a finite state automata without epsilon moves by $A'=(Q,\Sigma,q_{o},\delta',F)$ where $\delta'(q,\sigma)=CL^{\epsilon}(\delta(q,\sigma))$ for every $q\in > Q,\sigma\in\Sigma$. Prove...

I wrote:

Claim: $\forall w\in\Sigma^{+}:\,\forall q\in > Q:\,\delta'(q,w)=\hat\delta(q,w)$

The TA wrote that this claim is only true for $q_{0}$, why ?

I wrote a proof using induction on $|w|$:

Base case: $|w|=1:$

$|w|=1\implies\exists\sigma\in\Sigma:\, w=\sigma$.

$\forall q\in Q :\delta'(q,w)=\delta'(q,\sigma)=CL^{\epsilon}(\delta(q,\sigma))$

$\hat\delta(q,w)=\hat\delta(q,\sigma)=CL^{\epsilon}(\delta(q,\sigma))$

This was also marked as wrong.

Can someone please help me understand why my claim was wrong, and why my proof for the base case is also wrong ?

-
You want \hat\delta to get $\hat\delta$. –  Brian M. Scott Oct 17 '12 at 12:35
What's $\hat{\delta}$? Is this some sort of transitive closure? And what does $\in>$ mean? –  fgp Oct 17 '12 at 12:37
@BrianM.Scott - thank you –  Belgi Oct 17 '12 at 12:43
@fgp - $\hat\delta$ is transitive closure of $\delta$. the other thing was a typo, fixed. thank you for pointing it out –  Belgi Oct 17 '12 at 12:45
You also left out the part where it says what you actually want to prove about the modified automaton. I guess you want to prove that they accept the same language, is that right? –  fgp Oct 17 '12 at 12:57