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$
4
  • $\begingroup$ What specifically have you tried? What exactly is your trouble? $\endgroup$
    – Raphael
    Oct 9, 2017 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, 2017 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, 2017 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, 2017 at 5:29

2 Answers 2

3
$\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$
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$

Your Answer

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