# NFA for $L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) and ...$

The question asks to write a NFA for the following language $$L$$ above $$\Sigma = \left \{0,1 \right \}$$.

$$L = \{\sigma_1 u \sigma_2 v \sigma_3 \mid (\sigma_1, \sigma_2, \sigma_3 \in \Sigma, u, v \in \Sigma^*, |u| = |v|) \text{ and } (\sigma_1 = \sigma_2 \text{ or } \sigma_3 = \sigma_2 \text{ but not both})\}$$

The NFA must contain at the most 7 states.

To be honest, I spent a lot of time with the pumping lemma in order to disprove the claim that the $$L$$ is regular but it didn't work.

I came up to the conclusion that a word $$w \in L$$ must hold that $$|w| = 2n +3 : n \in \mathbb{N}\cup\left \{ 0 \right \}$$ and it led me to the following NFA:

This NFA doesn't cover the cases where $$\sigma_1 = \sigma_2 = 0 , \sigma_3 = 1$$ and $$\sigma_1 = 0 , \sigma_2 = \sigma_3 = 1$$.

The constrain of the 7 states prevents me from thinking furthermore.

The question wasn't designed to implement Myhill–Nerode theorem to come up with the solution.

I would like to know what can be added to the NFA I draw, or perhaps I'm not even in the right direction.

• Another issue that I can observe is that your NFA does not require $|u|=|v|$, but that $|u|=2x$ and $|y|=2y$ for some $x,y \in \mathbb{N} \cup \{0\}$ (i.e. that each string contains an even number of characters). Commented Apr 18 at 14:18

It is indeed regular. Here, your language is basically $$1(0+1)^{2m+1}0 + 0(0+1)^{2m+1}1$$ for all integers $$m \ge 0$$. We are basically fixing $$\sigma_1 \ne \sigma_3$$, and then let $$|u\sigma_2v|$$ be an odd cycle. This will automatically ensure the rest of the constraints are met. This is easily realizable by a NFA with 8 states, as shown below.
• Your automaton recognizes $011111$ which is not in the language: using three states for a loop will recognize words like $01^{3m+1}1$, not $01^{2m+1}1$. Commented Apr 18 at 14:59
• Stings like 011111 are not possible. All accepted strings are of odd length, and they start and end with different symbols. Commented Apr 18 at 15:15
• Now you just need to delete $q_3$ and $q_6$ and put the corresponding transitions from $q_2$ and $q_5$! Commented Apr 18 at 16:32