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$
$\endgroup$
5
-
$\begingroup$ 0101 matches the second part of the expressions. $\endgroup$– StevenOct 31, 2021 at 11:43
-
$\begingroup$ The language corresponding to a regular expression is described on Wikipedia. $\endgroup$– Yuval FilmusOct 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$– Kiruphasankaran NatarajOct 31, 2021 at 13:45
-
$\begingroup$ 010 also matches your re, that why the tool you're using reports that match. $\endgroup$– StevenOct 31, 2021 at 15:55
-
$\begingroup$ The evaluation is (0*(10))|((01)(01)*), so one of $00\cdots10$ or $0101\cdots01$. $\endgroup$– user16034Mar 30, 2022 at 14:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$
answered Oct 31, 2021 at 12:02