Question

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]. )

Answer 1

`\epsilon`, ba, aba, baba, ababa, baaba, abaaba, bababa, abababa, baababa, babaaba

Step-by-step explanation:

`S=\{aba, ba\}^*` 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
`\epsilon`).

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:
`\epsilon` (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:

`\epsilon`, ba, aba, baba, ababa, baaba, abaaba, bababa, abababa, baababa, babaaba