2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Try applying Myhill–Nerode theorem. $\endgroup$
    – Ariel
    Mar 29 at 9:52
3
$\begingroup$

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

example

$\endgroup$
11
  • $\begingroup$ Hi, I think you're right. Just updated the question - how about NFA? $\endgroup$
    – Galyoss
    Mar 29 at 11:00
  • $\begingroup$ When you say "However, no DFA for $L$ exists.", it could be confusing. You should add "with $O(\log |\Sigma|)$ states". $\endgroup$
    – Nathaniel
    Mar 29 at 11:43
  • $\begingroup$ @Nathaniel, thanks! $\endgroup$
    – Steven
    Mar 29 at 11:47
  • $\begingroup$ @steven, thank you! $\endgroup$
    – Galyoss
    Mar 29 at 11:51
  • $\begingroup$ @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 ? $\endgroup$
    – Galyoss
    Mar 29 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.