0
$\begingroup$

I tried to prove this by starting at RHS:

$$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$
But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful.
Any ideas?

$\endgroup$
3
  • $\begingroup$ The question in the title is different from the question in the body. Im assuming you made a writing mistake in the title $\endgroup$
    – nir shahar
    Jun 27 at 14:54
  • $\begingroup$ Or did you mean that this is what you tried to show, as a process of proving the question in the title? $\endgroup$
    – nir shahar
    Jun 27 at 14:55
  • $\begingroup$ @nirshahar Yes this was the process. $\endgroup$ Jun 27 at 14:56
0
$\begingroup$

We will not use regex equivalences, but rather show this directly by showing language equality:

First, we want to show that $L((aa^*bb^*)^*)\subseteq L(\epsilon + a(a+b)^*b)$: Take any word $w\in L((aa^*bb^*)^*)$. Its not hard to show that either $w=\epsilon$, or $w$ must start with $a$ and end with a $b$ (rewrite $bb^*$ as $b^*b$, it will help to prove this). Then, it will be clear that $w\in L(\epsilon+a(a+b)^*b)$.

Now we want to show that $L(\epsilon + a(a+b)^*b)\subseteq L((aa^*bb^*)^*)$: Take any word $w\in L(\epsilon + a(a+b)^*b)$. If $w=\epsilon$ its obvious why $w\in L((aa^*bb^*)^*)$. Otherwise, prove by induction over $|w|$ the length of $w$, that you can split $w$ in the following way: $$w=x_1x_2,\dots,x_k$$ for some $k\in\mathbb{N}$ such that $x_i \in L(aa^*b^*b)$.

Hint: define $x_1$ to be the substring of $w$ starting at the first element, and stopping at the first index $l$ such that $w_l=b$ but $w_{l+1}=a$. If there is no such index $l$, then take $x_1:=w$.

$\endgroup$
2
  • $\begingroup$ Oh sorry . Please delete this answer because I forgot to add epsilon on right side. I edited my question. Please make an answer for that if you can . Thanks again. $\endgroup$ Jun 27 at 15:02
  • $\begingroup$ @program_craft Sure. Im not sure how regex equivalences will solve it, but if you are allowed to directly talk about the language of the regex then it might be possible. $\endgroup$
    – nir shahar
    Jun 27 at 15:12

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.