Given the regular expression (1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 ), how many distinct strings would this evaluation produce? How is the word "distinct" interpreted within the regex context? Could you kindly explain?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Here are some of the strings it matches (with e for epsilon):
removing the epsilon
hi-lighted are the ones that were counted twice.
To count the number of strings it matches without duplicates we can count the number of length 1, length 2, length 3 and length 4 strings it matches (and add them). Each of these are 2^1, 2^2, 2^3, 2^3 so the sum is 2^4-1 = 31.