I'm having some trouble understanding the regular expression $0^*10|01(01)^*$. The expression matches strings like $00010$. But for some reason, I wasn't able to find a string that matches the $(01)^*$ at the end. An equivalent expression with capturing groups to demonstrate the order of evaluation would be very much helpful.

  • $\begingroup$ 0101 matches the second part of the expressions. $\endgroup$
    – Steven
    Oct 31, 2021 at 11:43
  • $\begingroup$ The language corresponding to a regular expression is described on Wikipedia. $\endgroup$ Oct 31, 2021 at 12:01
  • $\begingroup$ @Steven when I tried the string 0101 with the online tool regextester, it returned a match only for the first three characters, i.e., 010 and the 1 at the end doesn't seem to match. $\endgroup$ Oct 31, 2021 at 13:45
  • $\begingroup$ 010 also matches your re, that why the tool you're using reports that match. $\endgroup$
    – Steven
    Oct 31, 2021 at 15:55
  • $\begingroup$ The evaluation is (0*(10))|((01)(01)*), so one of $00\cdots10$ or $0101\cdots01$. $\endgroup$
    – user16034
    Mar 30, 2022 at 14:24

1 Answer 1


For a regular expression $r$, the regular expression $r^*$ matches all words of the form $w_1 \ldots w_n$, where $w_1,\ldots,w_n$ are matched by $r$ (possibly $n = 0$). For example $01$ matches only the word $01$, and so $(01)^*$ matches the words $\epsilon, 01, 0101, 010101, \dots$


Your Answer

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

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