0
$\begingroup$

Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. I was wondering if anyone could help me with this? thanks

$\endgroup$
  • $\begingroup$ What specifically have you tried? What exactly is your trouble? $\endgroup$ – Raphael Oct 9 '17 at 5:44
  • $\begingroup$ what i tried to do is break it down as so: L((x+y)*) = L(x)* or L(y)* = {x}* or {y}* = {x,y}*, then for the L(xy)* = L(x*)*.L(y*)* = L(x*).L(y)* = {xy}*. But it ended up not working out. $\endgroup$ – user78405 Oct 9 '17 at 22:28
  • $\begingroup$ "L((x+y)*) = L(x)* or L(y)* = {x}* or {y}* = {x,y}*" -- I don't know exactly what you mean here (logic needs parens, too!) but I can't read in a way that's correct. $(x+y)^*$ is not equivalent to $x^* + y^*$ (for all $x$, $y$). $\endgroup$ – Raphael Oct 10 '17 at 7:27
  • $\begingroup$ You can refer this answer, prove using Finite automata :stackoverflow.com/questions/8961632/… OR pages.cpsc.ucalgary.ca/~eberly/Courses/CPSC313/Syllabus/… for detailed proceudre and understanding $\endgroup$ – Pragya Oct 12 '17 at 5:29
2
$\begingroup$

First prove that every word in R1 is also in R2; then prove that every word in R2 is also in R1. Spend some time on each and see what progress you can make.

$\endgroup$
2
$\begingroup$

Proving equivalence of regular expressions can be tedious, so let me recommend two different strategies.

  1. Convert both expressions into regular grammars using the algorithm from the equivalence proof. Then prove them equivalent.

  2. Even more mechanical: convert both expressions into finite automata (using the algorithm from the equivalence proof). Showing equivalence is now moslty an algorithmic task the solution for which you should have seen in class.

    Determinise, minimize, show that they are isomorphic.

$\endgroup$

Your Answer

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