# Simplification of regular expression

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)*

Erik

• Do you have any particular reason to believe that it does implify much? – David Richerby Jun 12 '18 at 20:07
• Well, I have an assignment where I am supposed to do it, so it should be possible to do it. But I have a hard time to see how to start. I tried to create a minimal DFA, but it did not simplify the regular expression. – Erik Jun 12 '18 at 20:35

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.

• Honestly, the last one (stare at it, figure out the language, write a fresh regexp) is usually as effective as anythign else. Sad, but true. – David Richerby Jun 12 '18 at 22:32

It is indeed possible to simplify your expression. Proceed as follows:

(1) Compute the minimal automaton of your language:

(2) Observe that your language is $P^*0(11)^*$, where $P^*$ is the label of all paths from $1$ to $1$. Then $P$ is known to be a prefix code, which is easy to compute by unfolding the minimal automaton:

Thus $P = (01^*0 + 1)$ and your language is $(01^*0 + 1)^*0(11)^*$.

• This method using this tree is intuitive but is it related to any method to create a shift-reduce parser without reduce moves. – Deep Joshi Jun 15 '18 at 7:02