Consider the set

A = fa; ab; aabg;

a set of strings over the alphabet fa; bg. For strings, we have an interesting notation to define the universal

set U in this context. We take U defined by the Kleene closure (*) of the alphabet:

U = fa; bg =

[

i0

fa; bgi = fa; bg0 [ fa; bg1 [ fa; bg2 [ : : :

Answer the following questions about this statement.

3(a) What is the shortest string in the universe for A?

3(b) Write the contents of fa; bg0 [ fa; bg1 [ fa; bg2 in roster notation.

3(c) Write the contents of AA in roster notation. Note that when paring up the strings, you are concatenating

the strings. Your final answer should not contain any pairs, only strings, and should not contain

any duplicates.

Last

\f