2
$\begingroup$

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?

enter image description here

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

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ 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^{*}$. $\endgroup$ – Luke Mathieson Nov 2 '12 at 8:23
  • $\begingroup$ Second question: The DFA should accept $abbaa$ but it does not (I guess, since a lot of arrows are missing). $\endgroup$ – A.Schulz Nov 2 '12 at 8:27
  • 1
    $\begingroup$ Have you got to the systematic method of converting REs to NFAs yet? $\endgroup$ – Luke Mathieson Nov 2 '12 at 8:31
  • $\begingroup$ @LukeMathieson no i havent reached that part of course yet. $\endgroup$ – Rafay Zia Mir Nov 2 '12 at 8:46
  • $\begingroup$ @A.Schulz is my edited FA correct? $\endgroup$ – Rafay Zia Mir Nov 2 '12 at 8:50
6
$\begingroup$

At the point of writing, your NFA is still a bit off. One version of a correct answer looks like this: enter image description here

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 key thing to practice when doing things this way is breaking the RE down into a sequence of smaller REs, that you then stick together. This is essentially a 'casual' version of the systematic method.

The systematic way is simple, but a bit fiddly. It's a relatively long explanation as to how to do it systematically, and as you haven't reached that bit in your reading yet, I'll refrain from working through the details here, however just as a quick reference, this explanation is pretty thorough and reasonably well explained.

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael♦ Nov 2 '12 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.