DFA, RE, and NFA have equal expressive power.

• Every DFA can be converted into an equivalent RE
• Every RE can be converted into an equivalent NFA
• Every NFA can be converted into an equivalent DFA

Today we will take a NFA and convert it into a DFA.

abba will leave you in states 1 and 3.

Our NFA:

#states
empty
13
2
23
3
123
#initial
13
#accepting
13
123
#alphabet
a
b
#transitions
13:a>13
13:b>2
2:a>23
2:b>3
23:a>123
23:b>3
3:a>13
3:b>empty
123:a>123
123:b>23
empty:a>empty
empty:b>empty

This is now a legal DFA, except the accept state. So, any accept state in the NFA is also a DFA accept state:

Legal!