Number of distinct strings in regular expression

Question

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?

Answer 1

Here are some of the strings it matches (with e for epsilon):

1111
e111
0111
1e11
ee11
0e11
1011
e011
0011
11e1
e1e1
...

removing the epsilon

1111
111
0111
111  !
11
011
1011
011  !
0011
111  !
11   !
...

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.