4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Do you have any particular reason to believe that it does implify much? $\endgroup$ – David Richerby Jun 12 '18 at 20:07
  • $\begingroup$ 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. $\endgroup$ – Erik Jun 12 '18 at 20:35
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Jun 12 '18 at 22:32
5
$\begingroup$

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

(1) Compute the minimal automaton of your language:

enter image description here

(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:

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.