patternMinor
Simplification of regular expression
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
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.
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.