# Convert regular expression to Automaton [duplicate]

I'm trying to construct a finite-state automaton from the following regular expression:

$$(a|ba)(a|ba)^*(b|ab)^*$$

I know that from $$(a|ba)$$

the automaton should look something like this:

automaton http://cdn.imghack.se/images/5ab1437745d2a53d4630619819074d6c.jpg

from $$(a|ba)^*$$

it should look like this I guess:

automaton2 http://cdn.imghack.se/images/e1dc6ac63c6d967086d1f40aebf62c51.jpg

and from $$(b|ab)^*$$

is pretty much the same as the last one, the thing is I don't know how to unite them in one automaton.

I would appreciate any help in this matter

PS: I'm sorry for the images I'm still learning how to work with the automata editor jflap...

## marked as duplicate by D.W.♦, Nicholas Mancuso, Juho, David Richerby, Luke MathiesonMay 6 '15 at 9:08

• As Mike says in his answer, you're very close. The steps are now the following: define two new states, a start state and a single accepting state; add $\epsilon$-transitions from the start state to the left-most state in your first automaton; add an $\epsilon$-transition from the right-most state of the first automaton to the top-most state in the second; similarly from the top-most state in the second to the corresponding state in the automaton not shown; and then from the corresponding state in the automaton not shown to the newly added final state (which is the only accepting state). – Patrick87 May 15 '14 at 15:33
Once you have marked those, its very simple: If you have the automaton $A_1$ for $(a|ba)$ and $A_2$ for $(a|ba)^*$, to get an automaton for $(a|ba)(a|ba)^*$, just add $\varepsilon$-transitions from all finite states of $A_1$ to the start state of $A_2$. (This is btw part of the Thompson-construction, in case you want to look it up :) ) If needed, you can then remove all $\varepsilon$-transitions.
If you directly want to construct a $\varepsilon$-free NFA, you can use Glushkovs construction.