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$
3
  • 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, 2018 at 7:26
  • $\begingroup$ Algebraic approaches are fickleish. You need to have a theorem for every =. $\endgroup$
    – Raphael
    Sep 15, 2018 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, 2018 at 11:02

1 Answer 1

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$
1
  • 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$ Sep 15, 2018 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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