I have a regex $R=\epsilon+1+(\epsilon+1)(\epsilon+1)^*(\epsilon+1)$ which has to be simplified by algebraic operations. As we can do,

$\epsilon+1+(\epsilon+1)(\epsilon+1)^*(\epsilon+1)=\epsilon+1+(\epsilon+1)^+=(\epsilon+1)^+$ but the answer is $1^*$.

Can anyone please help me to find this with step by step solution?


1 Answer 1


No. I'm not going to give a step-by-step solution, but here's a hint or two: $(\epsilon + 1)$ can generate either nothing or a 1; $(\epsilon + 1)(\epsilon + 1)$ can generate 0, 1, or 2 copies of 1. Take it from there.

  • $\begingroup$ I understand this. But since I am applying algebraic operations, so what will be the correct law for which I get $(\epsilon+1)^*=1^*$. Again as mentioned in question, can $(\epsilon+1)^+$ generate $1^*$? $\endgroup$
    – Manjoy Das
    Jun 7, 2021 at 19:23
  • 1
    $\begingroup$ @ManjoyDas you should go back to the definition of the Kleene star and the concatenation with the empty word, it will help understanding. $\endgroup$
    – Nathaniel
    Jun 7, 2021 at 19:58
  • $\begingroup$ $1^*$ consists of all strings of the form $1^n$, for $n=0, 1, 2, \dots$, as yopu probably know. Ask yourself, from $(\epsilon + 1)$ give you $n=0$?, can it give you $n=1$?, can multiple concatenations can give you $n=2$?, $n=3$?. $\endgroup$ Jun 7, 2021 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.