Question

Let $\mathbf{\sum }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}$. Let ${\mathbf{WW}}_{\mathbf{k}}\mathbf{=}\mathbf{\left\{}\mathbf{ww}\mathbf{|}\mathbf{w}\mathbf{\in }\mathbf{\sum }\mathbf{*}\mathbf{\text{\hspace{0.17em}and\hspace{0.17em}}}\mathbf{w}\mathbf{\text{\hspace{0.17em}is\hspace{0.17em}of\hspace{0.17em}length\hspace{0.17em}}}\mathbf{k}\mathbf{\right\}}$.

1. Show that for each$\mathbf{k}$ , no DFA can recognize${\mathbf{WW}}_{\mathbf{k}}$ with fewer than${\mathbf{2}}^{\mathbf{k}}$ states.
2. Describe a much smaller NFA for $\overline{{\mathbf{WW}}_{\mathbf{k}}}$, the complement of $\stackrel{}{{\mathbf{WW}}_{\mathbf{k}}}$.

Short answer

1. Any DFA for given language has at least$2^{\mathrm{k}}$ states.
2. A much smaller NFA for $\overline{{\mathrm{WW}}_{\mathrm{k}}}$, the complement of ${\mathrm{WW}}_{\mathrm{k}}$can be described.

Step-by-step solution

Explain DFA.

Deterministic Finite Automata is the computer model that has the definite next state. Nondeterministic Finite Automata has the several states, one of them can be the next state.

Show that for each k , no DFA can recognize WWk with fewer than 2k states.

a.

Consider the${\mathrm{WW}}_{\mathrm{k}}=\left\{\mathrm{ww}|\mathrm{w}\in \sum *\text{\hspace{0.17em}and\hspace{0.17em}}\mathrm{w}\text{\hspace{0.17em}is\hspace{0.17em}of\hspace{0.17em}length\hspace{0.17em}}\mathrm{k}\right\}$ language is at least of length$\mathrm{k}$ . Consider the two bit strings, $\mathrm{x}={\mathrm{x}}_1\dots {\mathrm{x}}_{\mathrm{k}}$ and $\mathrm{y}={\mathrm{y}}_1\dots {\mathrm{y}}_{\mathrm{k}}$, be some location such that ${\mathrm{x}}_{\mathrm{i}}\ne {\mathrm{y}}_{\mathrm{i}}$. One of the strings contains a 1 at the${\mathrm{i}}^{\mathrm{th}}$ position and other contains a 0. Assume that , $\mathrm{z}=0^{\mathrm{i}-1}$, then $\mathrm{z}$distinguish between the bit strings.

Hence, there exists$2^{\mathrm{k}}$ strings of length$\mathrm{k}$ , that can be mutually distinguish by the given argument.

Therefore, Any DFA for given language has at least $2^{\mathrm{k}}$states.

Step 3: Describe a much smaller NFA for WWk¯ , the complement of WWk.

b.

The language $\overline{{\mathrm{WW}}_{\mathrm{k}}}$, can be described as $\overline{{\mathrm{WW}}_{\mathrm{k}}}=\left\{\mathrm{ww}|\mathrm{w}\in \sum *\text{\hspace{0.17em}and\hspace{0.17em}}\left|\mathrm{w}\right|<\mathrm{k}\right\}$. The NFA can be build with exactly $\mathrm{k}+1$states and it recognizes the language $\overline{{\mathrm{WW}}_{\mathrm{k}}}$.

The NFA consists of the states corresponding to the last $\mathrm{k}$bits.

The machine starts from the initial state which is state 0, as it will travers 1 initial state which is state 0, as it will traverse 1 it understand that it is the $\mathrm{k}$bit from the finishing state of end state and proceed to state 1.

As it has reached on the state $\mathrm{k}$, it accepts the string if and only if the string contains$\mathrm{k}-1$ bits. It checks for$\mathrm{k}-1$ bits as it starts traversing from$0^{\mathrm{th}}$ index.

Therefore, A much smaller NFA for $\overline{{\mathrm{WW}}_{\mathrm{k}}}$, the complement of ${\mathrm{WW}}_{\mathrm{k}}$has been described.