1
$\begingroup$

I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.

I need to prove the following property using different Kleene star properties:

$$(a+b)^* = b^*(ab^*)^*$$

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ What have you tried? You say you know about building a minimized DFA as one way to prove that they are equal. Well, have you tried that? What happened when you did? $\endgroup$
    – D.W. ♦
    Jul 28 '16 at 17:49
  • 4
    $\begingroup$ You say you want to use "different Kleene star properties". Which properties are you willing to use? List them all. Why should any of us feel obligated to prove it that way, when we already know another valid way to do it (using minimized DFAs)? That might make for a good learning exercise for you, but not for a good question here. What progress have you made on your own? We want to help you understand concepts, not do exercises for you. As you haven't shown us any sign of progress nor any indication of what you're stuck on, you given us much to work with, so it's hard to know how to help. $\endgroup$
    – D.W. ♦
    Jul 28 '16 at 19:13
  • 3
    $\begingroup$ There is no standard list of properties of the Kleene star operator. You'll have to let us know what list you are using so that we can help you further. $\endgroup$
    – Yuval Filmus
    Jul 28 '16 at 20:15
  • $\begingroup$ As a hint, if you're using the usual Kleene algebra axioms, then it may be easier to prove equality by proving the two partial orders $(a+b)^* \le b^* (ab^*)^*$ and $b^* (ab^*)^* \le (a+b)^*$ separately. $\endgroup$
    – Pseudonym
    Jul 28 '16 at 23:55
  • $\begingroup$ @D.W. minimized DFA for both are same.it's just one final state having both transitions going towards itself. why I want to go for other way proof? Let me explain. In competitive exams we need to find whether different expressions are equal or not. The process of converting to DFA and minimizing is not a worthy option because of time constraint. Though I know its a Pspace problem still I need some tips how to convert it using some other lemmas we have. Like (a+b)*=(ab)* , (a+b)*=(a*+b*)* , (a+b)*=(a*+b)*, (a+b)*=(a+b*)*, (a*)*=a* etc. I am just trying to convert it logically. Thats it. $\endgroup$
    – ViX28
    Jul 29 '16 at 5:31
6
$\begingroup$

A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^* = (a^*b)^*a^*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free): $$ \begin{align*} (a+b)^* &= (b+a)^* && C2 \\ &= (b^*a)^*b^* && C11 \\ &= (\epsilon+b^*(ab^*)^*a)b^* && C12 \\ &= b^* + b^*(ab^*)^*ab^* && C9 \\ &= b^*(\epsilon + (ab^*)^*ab^*) && C8 \\ &= b^*(\epsilon + \epsilon(ab^*\epsilon)^*ab^*) && C6,C7 \\ &= b^*(\epsilon ab^*)^* && C12 \\ &= b^* (ab^*)^* && C7 \end{align*} $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ great!! thats what needed.. I think you missed a " * " in C6,C7 line. it should be (ab* ϵ)*. $\endgroup$
    – ViX28
    Jul 29 '16 at 13:29
  • $\begingroup$ Right, thanks for pointing out the typo. $\endgroup$
    – Yuval Filmus
    Jul 29 '16 at 13:30
-1
$\begingroup$

Applying kleen star on both side

((a+b)*) *= ( b * (ab*)*) *

But ((a+b)* )* = (a+b)* as we know (a*)* = a*

( b * (ab*)*) * = (b + (ab*))* as we know (a+b)* =(a* b*)*

I can use b* as empty string as its redundant.

Even if we are using b* as empty string the expression gives all strings of a's and b's. So using b* wont add new strings to the set.

So we can say

(b + (ab*))*= (b+a) * = (a+b)*

Proved

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Here's a proof that $a = a^*$. Apply Kleene star on both sides: $a^* = (a^*)^*$. Proved. $\endgroup$
    – Yuval Filmus
    Jul 29 '16 at 12:15

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.