# Simplification of regular expression and conversion into finite automata

This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. I want to create an FA for the regular expression

$\qquad \displaystyle (a+b)^* (ab+ba)^+a^+\;.$

My first question is that how we can simplify this expression? Can we we write the middle part as $(ab+ba)(ab+ba)^*$? will this simplify the expression?

My second question is whether the automaton given below is equivalent to this regular expression? If not, what is the mistake?

This is not a homework but i want to learn this basic example. And please bear me as a beginner.

• For the first, smaller question, yes, that's what $^{+}$ means, just like $^{\ast}$, but with at least one occurrence, so you can rewrite any $\omega^{+}$ as $\omega\omega^{*}$. – Luke Mathieson Nov 2 '12 at 8:23
• Second question: The DFA should accept $abbaa$ but it does not (I guess, since a lot of arrows are missing). – A.Schulz Nov 2 '12 at 8:27
• Have you got to the systematic method of converting REs to NFAs yet? – Luke Mathieson Nov 2 '12 at 8:31
• @LukeMathieson no i havent reached that part of course yet. – Rafay Zia Mir Nov 2 '12 at 8:46
• @A.Schulz is my edited FA correct? – Rafay Zia Mir Nov 2 '12 at 8:50

So this NFA is design in an ad hoc manner, but there's still some basic organisation to it. You can see that there's three basic bits, the $a,b$ loop on the start state, a forced $ab|ba$, followed by two 2-step loops, then a forced $a$ to the final state, with an $a$ loop. The first loop takes care of the $(a+b)^{\ast}$, the next little clump does the $(ab+ba)^{+}$, then the tail end does the $a^{+}$.
• The systematic way is even more fiddly if you diallow $\varepsilon$-transitions, which I have seen people do. In response to the question, it should be noted that equivalence of regular expressions can be checked by translating both into NFA, transforming those to DFA and then minimising the DFAs. The resulting automata isomorphic if and only if the original expressions were equivalent. – Raphael Nov 2 '12 at 12:16