Designing a DFA for L={vwv : v,w elements of {a,b}* and |v| =2}

  • Thread starter Thread starter francisg3
  • Start date Start date
  • Tags Tags
    Automata Finite
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
1 reply · 2K views
francisg3
Messages
31
Reaction score
0
L={vwv : v,w elements of {a,b}* and |v| =2}

I know that "v" can take either aa, ab, ba or bb as values. I also know that "w" can be any string containing "a" and "b". Overall, I know that the two first and two last characters must be identical. How would I show this in a DFA or even an NFA?


Thanks.
 
Physics news on Phys.org

Discussion

Think about which parts of the input the finite automaton must remember and how you can use that to keep a "running match" of the later part of the input. It may help to start with an automaton that accepts the language "vv" and see if you can modify that into one that accepts "vwv".