For each regular expression below over abc give i 3 shortes

. For each regular expression below over {a,b,c}, give (i) 3 shortest legal strings, and (ii) 3 shortest illegal strings.

a. (a | b)*(aa|bb|cc)*     

b. (ab | ba | c)+              

c. (a | bb)* | (aa)* | (ab)*

Solution

(i) 3 shortest legal strings

a. (a | b)*(aa|bb|cc)*

To find shortest legal strings, we need to see whether there is possibility for Epsilon to occur

Next 1 length strings and 2, 3 and so on.

b.

c.