1
$\begingroup$

x,y are regular expressions, prove this: (xy+x)$^*$x = x(yx+x)$^*$* (* in this expression is kleene star)

I am looking for a method that is applicable to prove such questions. I know that proof needs to show that:

1) (xy+x)$^*$x => x(yx+x)$^*$

2) x(yx+x)$^*$ => (xy+x)$^*$x

My attempt is like this:

1) (xy+x)$^*$x =

= x(y+epsilon)$^*$x by pulling x out -the x on the left is the one pulled out

= x(yx+x)$^*$ by distributing the last x

2) x(yx+x)$^*$

= x(y+epsilon)$^*$x by pulling the x out -the right x is the one pulled out

= (xy+x)$^*$x by distributing the first x

Does this make sense? Thanks!

$\endgroup$
  • 1
    $\begingroup$ Your answer is not correct. In both 1 and 2 you end up with x(y+epsilon)*x which can no longer contain an infinite amount of xs, unlike the initial regular expressions. $\endgroup$ – orlp Sep 15 '18 at 7:26
  • $\begingroup$ Algebraic approaches are fickleish. You need to have a theorem for every =. $\endgroup$ – Raphael Sep 15 '18 at 11:02
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Sep 15 '18 at 11:02
1
$\begingroup$

Conceptually, the simplest approach is:

  1. Convert both regular expressions to NFA.
  2. Determinise both NFA.
  3. Minimize both DFA.
  4. The regular expressions are equivalent if and only if the minimal DFA are isomorphic.

The requisite algorithms and theorems are taught in (about) every introducory class to formal languages resp. automata and can be found in (every) textbook on the topic. In fact, the point of this exercise probably was to come up with this approach, combining results from the course. Sorry for spoiling it.

$\endgroup$
  • 2
    $\begingroup$ I don’t think that this was the intended solution method. Rather, in some courses one of the subjects is regular expression identities. $\endgroup$ – Yuval Filmus Sep 15 '18 at 16:09

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.