2
$\begingroup$

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

I know long algorithmic procedures but since regex is large I tried a lot by substituting common patterns for some regex definition but didn't seem to help.

What can be done so that this regex can be converted to DFA easily.

$\endgroup$
  • 1
    $\begingroup$ "long algorithmic procedures" -- long? At least an NFA is easy to get. Have you tried? Not by hand, I mean, not necessarily. $\endgroup$ – Raphael Apr 1 '17 at 18:19
  • $\begingroup$ I tried and it is not easy to get to answer by hand at least not for me.I was hoping I might get to know trick from anyone here since books usually do not mention it. $\endgroup$ – Vishvajeet Patil Apr 1 '17 at 19:43
  • 1
    $\begingroup$ Don't confuse "easy" with "not a lot of work". This task is easy but not necessarily quickly done. $\endgroup$ – Raphael Apr 1 '17 at 22:32
  • $\begingroup$ @Raphael Yes you are correct . $\endgroup$ – Vishvajeet Patil Apr 2 '17 at 11:03
1
$\begingroup$

What can be done so that this regex can be converted to DFA easily?

Algorithmic methods are doomed, if you insist on a DFA. Your regular expression contains about sixty characters. Roughly speaking, any procedure for converting to an automaton is going to produce at least one state per character of the regular expression. That means you're going to end up with an automaton with at least sixty states, and it's probably going to be nondeterministic. Determinizing that naïvely is going to give you $2^{>60}$ states, which isn't quite as many as the number of atoms in the earth, but it's still an unmanageably huge number.

Do you really need a DFA? If, for example, you're trying to write a program that will accept strings that match this regular expression, it's straightforward to check if an NFA accepts a particular string: just scan along the string keeping track of the set of states the automaton could be in after each successive character. For a fixed automaton, this can be done in linear time.

If you do need a DFA, you're going to have to figure out what the regular expression does. Break it into chunks. $(a(aa|b)^∗ab|b)$ matches $b$, along with all strings that have an even number of $a$s, begin with $a$ and end $ab$. It's not too difficult to see that this language is matched by the following automaton (I've omitted a trap state that's reached if any character is read from state $q_3$):
automaton 1

If you stare at that for a moment, you'll realise that states $q_0$ and $q_2$ are the same (both say "if $a$, go to $q_1$; else, go to $q_3$") so we can reduce the automaton to the following.
automaton 2
You could also use algorithmic state-minimization techniques to avoid having to notice things like this.

You can probably produce similar automata for the various "top-level" chunks of the regular expression, and chain them together to get a DFA for the whole thing.

$\endgroup$
  • $\begingroup$ "Break it into chunks." -- exactly the same can be done algorithmically. There are four "top-level" expressions; convert each of them into DFA using standard techniques, combine, determinize again. Determinization may explode on you, yes, but it does not have to. We can always start thinking when it does. $\endgroup$ – Raphael Apr 1 '17 at 18:18
-1
$\begingroup$

Thinking outside the box: You can use implementations of an algorithm to convert this RegEx to a DFA easily. Looking for regular expression to DFA online in your favorite search engine will lead you pages that allow you to convert the expression within the page. This is very easy and will give you results within a minute.

$\endgroup$
  • $\begingroup$ The asker knows there are algorithms but feels that using them will be very time-consuming because the regular expression is very long. Also, the algorithms tend to produce nondeterministic automata and determinizing these leads to an exponential blowup in the number of states. None of this can be done "within a minute". $\endgroup$ – David Richerby Apr 1 '17 at 13:27
  • $\begingroup$ @DavidRicherby ... determinizing these can lead to an exponential blowup in the number of states. $\endgroup$ – Raphael Apr 1 '17 at 18:16
  • $\begingroup$ "The asker knows there are algorithms but feels that using them will be very time-consuming" - this is why I wanted to point to machines that execute the algorithms for us. There are RegEx-DFA converters online that give you the automata in a very short time. I actually did this (searching -> entering RegEx -> seeing the automaton) in less than a minute. The automaton had 26 states (the intermediate NFA had 63), but if necessary, implementation for minimization algorithms exist as well. Also, there was no constraint on size specified in the question, only the desire to reduce time consumption. $\endgroup$ – Mike B. Apr 3 '17 at 9:47

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.