Oh yea, I see what's my confusion now. In the first string, I didn't consider 11 and 0 matches the pattern without the repetition. Actually what I did is I entered the pattern and the test strings into kudos (a python regexp debugger) and got the match groups, which didn't have 11 and 0 as matches, although they do match the pattern "(0|1(01*0)*1)".
Thank you for the help. Leon wrote: > You are right. In fact the procedure is as follows: > The substr ``101101" is no problem, if stop here, match will > successful. > But the tailing `1' occurs, so we may imagine the working automata move > to a state, which according to the regexp's outer most `)', and ready > to repeat > the whole regexp again. In this case, the answer is ``yes" only when > there exists > at least two ``1", but only one here. > > BTW, the first string is matched exactly, according to your notion, it > should be written as: _11_0_1011101 -- http://mail.python.org/mailman/listinfo/python-list