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 this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input x is applied at state p and q.

How can I prove that

$p \overset{k}\equiv{} q$ iff $\forall x$ $|x|=k$, g(p,x)=g(q,x)

i.e state p is k equivalent to state q iff and only if the given condition above

My definition of k equivalence is $p \overset{k}\equiv{} q$ if $\forall x$ $|x|<=k$, g(p,x)=g(q,x)

share|improve this question
What is your definition of $\overset{k}\equiv{}$? Without more information it looks like what you've quoted is the definition, and therefore is not subject to proof. –  Henning Makholm Sep 26 '12 at 14:29
@user34790 Your definition doesn't make sense –  rajan sthapit Sep 26 '12 at 14:54
@Henning. I have given the definition –  user34790 Sep 26 '12 at 14:56

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.