World's most popular travel blog for travel bloggers.

How to reduce this regular expression?

, , No Comments
Problem Detail: 

I was converting a DFA to regular expression with the help of state equations and came up with this regular expression. How do I further reduce this regular expression? $$b+aaa^*b+abb^*+a$$ I can feel it's same as $$a^*b+ab^*$$ but how do I proceed to simplify the first one to the second mathematically?

Asked By : Samik
Answered By : D.W.

Minimizing a regular expression is PSPACE-hard. Therefore, if you're looking for a general set of techniques to minimize a regular expression, there's no good solution: there is no good set of techniques that always works and is always efficient. See http://cs.stackexchange.com/a/12278/755 and http://cs.stackexchange.com/a/43863/755 and http://cstheory.stackexchange.com/q/12361/5038.

Of course, none of these results rule out the possibility of techniques that work for your particular example or that sometimes work. However, they show that you shouldn't expect any general technique, i.e., any technique that works for all regular expressions and always gives the optimal answer and is asymptotically efficient.


That said, there are some ad-hoc methods you can use. For instance, by staring at it, you can quickly recognize that

$$abb^* + a = ab^*,$$

since $ab^* = a(b^*) = a(\varepsilon + b b^*) = a + abb^*$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47704

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback