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.
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?