# How to construct a NFA that the third symbol and the third from last symbol are same?

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!

• If you use the correct construction, then the "intersection" of NFA1 and NFA2 would certainly accept aba and aaa. – Yuval Filmus Feb 23 '17 at 20:17
• 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 – 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$: