Build a NFA that accepts $L_k=\{w\#w\quad |\quad w\in\{a,b\}^*,|w|=k\}$, where $\Sigma=\{a,b,\#\}$ i've been trying this for hours...
Let $$k\geqslant 1, \quad \Sigma=\{a,b,\#\}$$
$$L_k=\{w\#w\quad |\quad w\in\{a,b\}^*,|w|=k\}$$
Let's say that $A$ is a NFA that accepts $L_k$.
First of all, What's the minimum number of states in $A$ ?$\quad$
(HINT: For 2 different words $x\#x, y\#y\in L_k$, show that the k+1 state is different for each word)
Second, try to build a NFA $B$ with $O(k)$ states that accepts $\overline{L_k}$ - (meaning: $\Sigma^*\setminus L_k$ ) $\quad$
[HINT: Try to build 2 machines: one that accepts all words that are NOT from the form $x\#y: x,y\in \{a,b\}^k$ and the other that accepts all the words from the form $x\#y: x,y\in \{a,b\}^k, x\not=y$]
 A: First part revised 10 April 2021.
HINT: Call the NFA $M$. You need each $x\in\{0,1\}^k$ to take $M$ to a different state; show that this takes $\sum_{i=0}^k2^i=2^{k+1}-1$ states. This part of $M$ is actually deterministic and has half of the states. The other half will look the same in reverse. It will have one acceptor state (instead of one initial state). It will have two states feeding into that acceptor state, one for words $w\#w$ in which $w$ ends in $0$ and one for those in which $w$ ends in $1$. Each of those states will also have two states feeding into it, and so on. Finally, each of the $2^k$ states at the end of the front half of $M$ has a $\#$ transition to the appropriate one of the $2^k$ states at the beginning of the second half. With this design you end up with a total of $2(2^{k+1}-1)=2^{k+2}-2$ states.
The $2^k$ states reached via inputs $x$ with $x\in\{0,1\}^k$ must all be distinct, since $M$ must be able to distinguish these $2^k$ inputs. A $\#$ transition is needed out of each of them, and those transitions must retain the distinctions, so they must go to $2^k$ distinct states.
From each of those states there must be a unique path to an acceptor state, and a little thought shows that this means that if we reversed the transitions, there would have to be a unique path from an acceptor state to each of those states. This in turn means that if we made the initial state an acceptor state and made each of the acceptor states an initial state, we’d have another NFA, $M'$, that accepts $L_k$. It’s first half, which is the second half of $M$, would therefore need at least $2^{k+1}-1$ states.

The hint for the second problem points the way, though I wasn’t able to follow it exactly. The first of the two machines suggested can be made quite straightforwardly with $2k+3$ states. The second machine is a little trickier: the approaches that I found most obvious gave me $O(k^2)$ states. However, you can get one with $O(k)$ states that doesn’t quite match the description in the hint but is good enough.
In the initial state an input of $0$ gives it the choice of staying where it is or moving to a state $q_0$, and an input of $1$ gives it the choice of staying where it is or moving to a state $q_1$. From each of these states there is a chain of $k+1$ states, and the machine advances one state along the chain for each input. Finally, the $k$-th state in the chain from $q_0$ has only a $1$-transition to the last state in the chain, and the $k$-th state in the chain from $q_1$ has only a $0$-transition to the last state in the chain. The only acceptor states are the last states in the two chains. This machine accepts all words over $\Sigma$ that have a $0$ and a $1$ with exactly $k$ characters between them, and it has $O(k)$ states.
The first machine accepts every word that is not of the form $x\#y$ for $x,y\in\{0,1\}^k$; the second machine accepts every word that is of that form but has mismatched characters in positions $\ell$ and $\ell+k+1$ for some $\ell\in\{1,\ldots,k\}$. (The second machine also accepts some words that are not of that form, but that’s all right.)
Now combine these two machines in an NFA that accepts the union of their languages
