Suppose the alphabet is {a,b}. I have tried coming up with NFA1: third symbol is a, and NFA2: third from last symbol is a. Then NFA3 and NFA4 similar but with symbol of b. Then I use intersection of NFA1, NFA2, and intersection of NFA3, NFA4, and add $\epsilon$ transition. But things seem to go wrong here. When doing the intersection of, say, NFA1, and NFA2, obviously the new NFA would not accept strings such as aba, aaa.

I have been trying different methods but still stuck here for hours. Any help of hint would be much appreciated!

  • 1
    $\begingroup$ If you use the correct construction, then the "intersection" of NFA1 and NFA2 would certainly accept aba and aaa. $\endgroup$ – Yuval Filmus Feb 23 '17 at 20:17
  • $\begingroup$ The way you're attempting should work, but NFA intersection is tricky. If it helps, a regex is ..a(.*a)?..|..b(.*b)?..|.aa.|.bb.|a.a|b.b $\endgroup$ – Matt Timmermans Feb 24 '17 at 3:05


Here is a NFA that accepts exactly those strings whose first and last character are both $a$:

enter image description here

Can you modify and extend this to become a solution to your problem?

  • 1
    $\begingroup$ Would even work without epsilon edges. $\endgroup$ – Hendrik Jan Feb 23 '17 at 20:58

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.