3

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$]

Jay
  • 107
ryden
  • 583
  • The hint for the first part is confusing; for a nondeterministic automaton, what does "the $k+1$ state mean? I think the idea is that, for each word $x$ of length $k$, there is a state $s$, reachable with input $x$#, such that a further input $x$ can lead from $s$ to an accepting state but any further input $y\neq x$ cannot lead from $s$ to an accepting state. In particular, different choices of $x$ must correspond to different states $s$. – Andreas Blass Mar 31 '21 at 16:30

1 Answers1

4

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

Brian M. Scott
  • 616,228
  • for the first part of your comment, can't the accepting states collapse to one state? so that the number of states is $2^{k+1}-1+k2^k+1=(k+2)2^k$ ? – Bernard Apr 10 '21 at 16:46
  • @Benny: You’re absolutely right; thanks! – Brian M. Scott Apr 10 '21 at 19:22
  • I don't think this is true either. take the case were $k=2$, then this automaton has only $14$ states, were $(k+2)2^k=16$. Please help me to justify in a proof why it is. – Bernard Apr 10 '21 at 23:20
  • 1
    @Benny: In fact now that you’ve got me thinking seriously about it again, I see that we can get down to $2^{k+2}-2$: the back half is a mirror image of the front half, and the $#$ transitions make sure that a $w$ path on the front half matches up with a $w$ path on the back half. I’m doing a couple of things right now, so it may take me a bit to get it rewritten properly, but I’ll definitely do it this evening. – Brian M. Scott Apr 10 '21 at 23:34
  • @Benny: Sorry: I had to be away for most of the day, and I’ve not had time to work up a better sketch of the argument, but I did want to get something posted before calling it a night. – Brian M. Scott Apr 11 '21 at 08:58
  • thanks for that :) – Bernard Apr 11 '21 at 09:09
  • @Bernard: You’re welcome. – Brian M. Scott Apr 11 '21 at 22:06