0
$\begingroup$

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:

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ Commented Apr 18 at 14:18

1 Answer 1

2
$\begingroup$

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.8 state NFA

PS: I hope this simplification might lead to your required 7 state solution, which I cannot visualize at this moment.

$\endgroup$
11
  • $\begingroup$ 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$. $\endgroup$
    – Nathaniel
    Commented Apr 18 at 14:59
  • $\begingroup$ Sorry my mistake, I am updating the answer $\endgroup$
    – codeR
    Commented Apr 18 at 15:11
  • $\begingroup$ Stings like 011111 are not possible. All accepted strings are of odd length, and they start and end with different symbols. $\endgroup$
    – codeR
    Commented Apr 18 at 15:15
  • $\begingroup$ Now you just need to delete $q_3$ and $q_6$ and put the corresponding transitions from $q_2$ and $q_5$! $\endgroup$
    – Nathaniel
    Commented Apr 18 at 16:32
  • $\begingroup$ @codeR Thank you very much. I also can't visualize 7 states but what you came with is very useful !! $\endgroup$
    – Daniel
    Commented Apr 18 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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