3
$\begingroup$

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?

1 Answers 1

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.