# NFA for words which start and end with different letters with $O(\log(| \Sigma |))$ states

I'm trying to build a NFA for the following language $$L = \{ \sigma_1 \sigma_2 \sigma _3 \ldots \sigma _n \mid \sigma _1 \neq \sigma _n \}$$. The catch is that for $$\Sigma$$ such that $$|\Sigma|=2^k$$, the NFA should have $$\Theta(k)$$ states.

I was thinking of representing the letters in binary but I'm not sure what I should do exactly.

• Try applying Myhill–Nerode theorem. Mar 29 at 9:52

The original question referred to DFA (and not NFAs). However, no DFA for $$L$$ with $$O(k)$$ states exists.

Consider $$\Sigma$$ as a set of words (i.e., each word consists of a single character from $$\Sigma$$). Given any two distinct words $$a,b \in \Sigma$$, the word $$a$$ is a distinguishing extension for $$a$$ and $$b$$. I.e., $$aa \not\in L$$ but $$ba \in L$$.

This shows that the number of equivalence classes of $$L$$ w.r.t. the equivalence relation "not having a distinguishing extension" is at least $$|\Sigma|$$. By the Myhill-Nerode theorem, any DFA for $$L$$ must have at least $$|\Sigma|$$ states.

The idea to build a NFA with $$O(k)$$ states is as follows: in addition to an initial state $$s$$, and to an accepting final state $$t$$ there are $$2k$$ states indexed with $$1, \dots, 2k$$.

Assign a distinct integer $$x_a$$ from $$0$$ to $$2^k-1$$ to each character $$a \in \Sigma$$ and consider the binary string $$b_a$$ of length $$2k$$ obtained by concatenating the binary string of length $$k$$ representing $$x_a$$ in binary, with its complement.

For each character $$a \in \Sigma$$ let $$S_a$$ be the set of all states $$i$$ such that the $$i$$-th least significant bit in $$b_a$$ is $$1$$, and define $$\overline{S}_a = \{1, \dots, 2k\} \setminus S_a$$.

For each $$a \in \Sigma$$, add the following transitions:

• A transition from $$s$$ to each state $$i \in S_a$$.
• A transition from each state $$i \in \{1, \dots, 2k\}$$ to itself.
• A transition from each state $$i \in \overline{S}_a$$ to $$t$$.

Given a word $$\sigma_1, \sigma_2, \dots, \sigma_n$$ with $$\sigma_1 \neq \sigma_n$$, let $$i$$ be an index such that the $$i$$-th least significant bit of $$b_{\sigma_1}$$ is $$1$$ while the $$i$$-th least significant bit of $$b_{\sigma_n}$$ is $$0$$ (such an index always exists). Then, $$s \to i \to i \to \dots \to i \to t$$ is an accepting path in the NFA.

Conversely, any accepting path is of the form $$s \to i \to i \to \dots \to i \to t$$ for some $$i$$. This implies that $$i \in S_{\sigma_1} \cap S_{\sigma_n}$$, i.e., $$b_{\sigma_1}$$ and $$b_{\sigma_n}$$ differ (at least) on the $$i$$-th least significant bit. This shows that $$\sigma_1 \neq \sigma_n$$.

The number of states of the NFA is $$2k+2$$.

Here is an example for $$\Sigma = \{x,y,z,w\}$$. All edges for which no label is shown are actually labelled with $$x,y,z,w$$.

• Hi, I think you're right. Just updated the question - how about NFA? Mar 29 at 11:00
• When you say "However, no DFA for $L$ exists.", it could be confusing. You should add "with $O(\log |\Sigma|)$ states". Mar 29 at 11:43
• @Nathaniel, thanks! Mar 29 at 11:47
• @steven, thank you! Mar 29 at 11:51
• @steven, by saying "it's complement" (line 3) - do you mean change each bit in $x_a$ ? for example, if a is 00100, then $b_a$ will be 0010011011 ? Mar 29 at 11:59