Objective is to create DFA from a regular expression and using \"Regular exp>NFA

Question

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that?

I asked this question to our professor but he told me that we can use intuition and kindly refused to provide any explanation. So I wanted to ask you.

"Regular exp>NFA>DFA conversion" is not an option because such a conversion takes a lot of time to convert a rather complex regular expression. For example, for a certain regex "regex>NFA>DFA" takes 1 hour for a human being. I need to convert regex to DFA in less than 30 minutes.

Explanation / Answer

J.-E. Pin provides the better answer in terms of formality and completeness, but I think there's something to be said for the "intuition" that your professor is hinting at.

In most of these cases, the easiest thing to do is to look at a regular expression, understand what language it's accepting, then use your creativity/cleverness to construct a DFA accepting that language.

There's no straightforward way to do this, other than the algorithms others have given, but here are some guidelines that might prove useful.

Ask yourself, could I write a program that accepts this RE using only boolean or very small integer variables? Then write that program, and convert it into a DFA where there's a state for every combination of values.

Look for parts of the regular expression that you know you can accept deterministically, where you know "If I see this, then I must be matching this part of the RE." There won't always be tons of these, but identifying these parts can show the parts that will be easy to make a DFA, so you can spend more time on the parts that really require non-determinism.

The subset construction for NFA->DFA isn't actually that complicated of an algorithm. So if this is an assignment, not an exam question, it might be faster to just code up an implementation, and let your program convert NFA to DFA. If you used your own code, there shouldn't be any plagarism issues.

Remember that no matter what you do, any technique will blow up exponentially in the worst case (unless you find a polynomial algorithm for this, in which case, congratulations, you've proved P=NP=PSPACE and you're now a millionaire.)

Try to "look ahead," cut corners when you can use your intuition in places when the algorithm would require many steps but its result is clear.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.