Prove $(a+ba)^*ba = (a^*ba)^+$ and $(a+b(ab)^*aa)^* b(ab)^*a = (a^*ba)^+$

1k Views Asked by At

I'm 100% sure that both these regular expressions are same since it produces an exactly same set of strings, but I'm unable to prove it mathematically. Can someone please provide me with a step by step solution of the prove?
Prove:
1)(a+ba)*ba = (a*ba)^+
2)(a+b(ab)*aa)*.b(ab)*a = (a*ba)^+
I tried using these identities:
RR* = R*R R*R* = R* (R*)* = R* RR* = R*R (PQ)*P =P(QP)* (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* =a*(ba*)*

1

There are 1 best solutions below

1
On BEST ANSWER

Rules we are going to use. I hope I didn't miss anything.

  1. $(P+Q)^* = P^*(QP^*)^*$.
  2. $(PQ)^*P =P(QP)^*$.
  3. $P^* = \varepsilon+P^+$.
  4. $P^+ = P^*P = PP^*$.
  5. $PQ + PR = P(Q+R)$ and $PQ + RQ = (P+R)Q$.
  6. $\varepsilon P = P = P \varepsilon$.

Let $c = ba$.

For the first identity, we have:

$$(a+ba)^{*}ba = (a+c)^*c \stackrel{(1)}{=} a^*(ca^*)^*c \stackrel{(2)}{=} (a^*c)^*a^*c \stackrel{(4)}{=} (a^*c)^{+} = (a^*ba)^{+}$$

For the second identity, notice $$b(ab)^*a \stackrel{(2)}{=}(ba)^*ba = c^*c \stackrel{(4)}{=} c^{+}$$ we have

$$\begin{align}(a+b(ab)^*aa)^*b(ab)^*a &= (a+c^{+}a)^*c^{+}\\ &\stackrel{(6)}{=} (\varepsilon a + c^{+} a)^*c^{+} \stackrel{(5)}{=} ((\varepsilon+c^{+})a)^*c^{+}\\ &\stackrel{(3,4)}{=} (c^*a)^*c^* c\\ &\stackrel{(2)}{=} c^*(ac^*)^*c \stackrel{(1)}{=} (a+c)^*c \stackrel{(1)}{=} a^*(ca^*)^*c\\ &\stackrel{(2)}{=}(a^*c)^*a^* c \stackrel{(4)}{=} (a^*c)^{+}\\ &= (a^*ba)^+ \end{align}$$