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?
Number of distinct strings in regular expression
3
$\begingroup$
regular-expressions
1 Answers
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.