Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.