The strings not processed successfully are 1, 2, and 3. Only string 4 is processed successfully.
I think your problem is not with interpreting the meaning of regular
expressions, but in understanding the process of lexical analysis, at
least as intended in your course.
Normally, a regular expression is supposed to match a string from
beginning to end. But when doing lexical analysis of a program, you
are supposed to cut the program text in small chunks coresponding to
the lexical elements of the language, which in turn can be taken (up
to some details not relevant here) as the terminal alphabet of the
(usually Context-Free) grammar used to define the language you are parsing.
So, during lexical analysis, you have nothing to indicate the end of a
lexical element, as the program text goes on to give the next lexical
element. For example, if you are scanning the string $foobar$, is it
the identifier $f$ followed by $oobar$, or $foo$ followed by $bar$, or
$fo$ followed by $oba$ and $r$. For a strict lexical point of view,
all these possibilities would be correct ... though the grammatical
parser that will use the lexical element can be unhappy with some
To simplify matters, a simple rule is often followed by scanners performing lexical analysis, called maximal munch rule, or longest match rule. It works as follows:
While recognizing a lexical element, the lexical analyzer
will keep reading the input string as long as it is reading a prefix
of a lexical element, according to the lexical specification, and will
halt when the next symbol to be read would no longer constitute such a
prefix if added to the part of the input already scanned. At that
point, if the scanned string corresponds to a complete lexical element
(i.e. the scanning automaton is in an accepting state), this lexical
element has been recognized. If it is only a prefix of a lexical
element that cannot be completed with what follows into a proper
lexical element, you have a lexical analysis error.
Thus with your example 1, $0111110$, the lexical analyser will start
recognizing the second regular expression $01^+$, and will scan
$011111$ as one lexical element. Then it is left with only $0$ which
is the prefix of a word in the first two regular expression $(00)^*$
and $01^+$. But then the string stops, so that it cannot be part of a
complete lexical element. hence the lexical analysis fails with an
error at that point.
You could say that if you had stopped the first lexical element one
symbol earlier, thus recognizing $01111$. Then you would be left with
$10$ which is recognizable by the third regular expression $10^+$. But
that is not how things work. There is no backtracking (actually, some scanners have more complex rules allowing for some backtrack, for example for the programming language C). Allowing this
would also make thigs a lot more ambiguous as I explained in the
In the second example $01100110$, you get $011$, then $00$, and you
are left with $110$. The first $1$ is a prefix for the regex $10^+$,
but it should then be followed by at least one $0$, which is not
there. Hence lexical analysis fails.
However, the third example $0001101$ should fail too. The reason is
that symbols are read one by one. The first $0$ is a prefix for both
regex $(00)^*$ and $01^+$. But, on scanning the second $0$, we know we
are looking for a lexical element defined by the forst regex
$(00)^*$. Then the third $0$ is ok too, since $000$ is a prefix of
$0000$ which is recognized by the first regex. So it is scanned. But
now we need a $0$, and we find a $1$. So the lexical analysis fails.
My guess is that the designer of the exercise recognize too quickly
that it could work, by stopping one $0$ early (and I did too the first
time I read this). But the computer does not have this global
perception, and proceeds one symbol at a time.
The fourth example $01100100$ works fine, yielding $011$, $00$, and $100$.
If backtracking were allowed, all four strings could be scanned into
But the fourth string could then be scanned as:
$011$, $00$, $100$, or
$01$, $10$, $01$, $00$
Though you can use a rule that you backtrack only in case of failure,
to avoid such an ambiguous situation.
Of course, there is the possibility that your instructor defined things differently, but this is the best I can do with the information I have.