2
$\begingroup$

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 \iff \forall x,|x|\le k, g(p,x)=g(q,x)$

  • 0
    @He$n$ning. I have given the definition2012-09-26

1 Answers 1

0

It seems that either you are asking for a proof of the definition (which is not subject to proof as it is not a proposition), or you are asking how to show $ \forall x, |x|= k, g(p,x)=g(q,x) \iff \forall x, |x|\le k, g(p,x)=g(q,x) $

This is trivially true in the backward direction, so I assume the question is $ \forall x, |x|= k, g(p,x)=g(q,x) \implies \forall x, |x|\le k, g(p,x)=g(q,x) $ which isn't trivial. This is the same as asking "If two automatons agree on all strings of length $k$, do they also agree on all strings of length less than $k$?". The answer to this question is "no". The following two automata are a counterexample.

enter image description here enter image description here

The two automata agree on all strings of length $2$ but do not agree on $a$ which is a string of length $1$.