Here is the regular expression I made for it
This is my first answer, used the naive method aka don't know what am doin' method. $$ \epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( (a|(b^*a))ba^*\right) \right) ^* $$
this is my re-worked answer, with the state removal method.
$$ \left( a^* \cup (b)(a \cup bb^*a) \right) ^* $$
steps taken :
- Add a new start state and a new final state.
- Add epsi transitions to the new states.
- Remove Q2
- Link between Q1 and Q3 is now $a \cup bb*a$
- Remove Q1
- Add a new link between Q0 and Q3 with $ (b)(a U bb*a)$ label
- Remove Q0 There are three paths. a*, the big regex and the start with epsi $\epsilon \cup a* \cup (b)(a \cup bb*a)$
- Remove Q3
- We get $\epsilon \cup \left( a^* \cup (b)(a \cup bb^*a) \right) ^*$ =$ \left( a^* \cup (b)(a \cup bb^*a) \right) ^*$
My questions are:
- Is my regular expression correct ?
- What happens if it loops ?
To be clear, let's say we have the string aababaaaaabab
I think that string is recognized by the NFA, but I'm not sure it is by my regular expression.
does the $^*$ at the end cover it correctly ?
ps: As suggested I moved this from math.se