Extremely Simple Regex Expression Clarification (10)*

Question

I feel bad about asking a question so simple, but I can't figure this out for the life of me. I need to construct a NFA based on some languages, and the only one I can't figure out is this one:

L = (10)*

Note that I am not asking for any help concerning the FSM, but only some clarification on what the language represents. Most of the other languages were presented to me in a more understandable fashion:

L = {w | w contains an even number of 0's } 

I'm thinking it's just a regular expression, and after some perusing of the regex cheat sheet, my only guess is that it matches for the group 10 0 or more times, but that clearly doesn't seem right because everything would match.

Any help is greatly appreciated.

Answer 1

Your belief about the meaning is basically correct, but it's not everything that would match.

Unlike your usual regex libraries, when we're dealing with language theory like this, a regular expression must match the entire string. So, ε (empty string) is in the language, 10 is in the language, 1010 is in the language, and so on - everything that consists entirely of the string "10" repeated 0 or more times.

01, however, is not in the language; the string does not consist of the string "10" repeated 0 or more times. 1 is also not in the language, you're missing the final 0.

I don't know if you've covered this part yet, but if you convert that regex to an NFA (or a DFA, non-determinism isn't required for this one) you'd basically get this (slightly simplified, if I remember my conversion algorithm correctly, but it's a pretty trivial change from the algorithm to this):

  1
 ┌─┐
 │ ↓
→a b
 ↑ │
 └─┘
  0

where a is an accepting state, and b is not.

Does this help you see why it doesn't match everything?

Answer 2

These strings are in the language (10)*:

<empty string>
10
1010
101010
10101010
(etc.)

These strings are not in the language (10)*:

0
1
01
11
010
01010
101
10101
(etc.)

Does that help?

Answer 3

Could this be of use? http://xenon.stanford.edu/~xusch/regexp/analyzer.html