List the first 11 elements of s = {aba, ba}∗ in canonical order. (note: the alphabet here is {a, b}, but the set s is being operated upon by the kleene star. remember to alphabetize each group of equal-length strings according to the alphabet [i. e., dictionary order]. )

, ba, aba, baba, ababa, baaba, abaaba, bababa, abababa, baababa, babaaba

Explanation:

is just the set of ALL strings that can be constructed through concatenation of the 2 strings "aba" and "ba" and the empty word (usually denoted as ).

Listing the first 11 elements of S is just listing the first 11 strings we can construct through concatenation of the strings "aba" and "ba". Canonical order is listing them alphabetically (dictionary order).

Strings of length 0: (the empty word)

Strings of length 1: We clearly cannot construct a string of length 1 using the strings "aba" and "ba".

Strings of length 2: ba

Strings of length 3: aba

Strings of length 4: baba (we concatenate 2 times the string "ba")

Strings of length 5: ababa, baaba (notice the first one is just aba+ba, and the second one is ba+aba, we put the one starting with an a first)

Strings of length 6: abaaba, bababa (notice the first one is just aba+aba, and the second one is ba+ba+ba)

Strings of length 7: abababa, baababa, babaaba (notice the first one is just aba+ba+ba, the second one is ba+aba+ba, and the third one is ba+ba+aba)

So our first 11 strings in alphabetical order are:

, ba, aba, baba, ababa, baaba, abaaba, bababa, abababa, baababa, babaaba