HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Simplification of regular expression

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
expressionregularsimplification

Problem

I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems.

How would one approach simplifying the following regular expression:

(01(11) (10+0)+00+1) 0(11)*

Thanks in advance,

Erik

Solution

Minimizing a regular expression is PSPACE-hard, so there is no general method that is generally applicable and can be completed in a reasonable amount of time. You'll need to inspect each individual situation on a case-by-case basis.

If you want to read about general methods, see https://cstheory.stackexchange.com/q/31630/5038 and https://cstheory.stackexchange.com/q/12361/5038. CSTheory has a nice blog post with an overview of the field. The alternative is to stare at that regular expression, understand very well what language it recognizes, and write down a shorter regexp. You might be able to find some simplifications that work for that particular case, even though they are not general.

Context

StackExchange Computer Science Q#93027, answer score: 7

Revisions (0)

No revisions yet.