Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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))$


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 ?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.