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

Answer:

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

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