Given k > 0, construct an NFA with at most 7k^2 states for the alphabet {0,1,2} where the language of the NFA is:
L = {ww' : |w| = |w'| = k, where w is not the same as w'}
The only way this is possible is to use non-determinism, but i am not really sure how. Any ideas?