2
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 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, 2017 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, 2017 at 3:05

1 Answer 1

Reset to default
4
$\begingroup$

Hint:

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?

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Would even work without epsilon edges. $\endgroup$
    – Hendrik Jan
    Feb 23, 2017 at 20:58

Your Answer

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

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