Kleene star proof: $(AA)^*$ is the set of strings from $A^*$ of even length

Question

Let $A$ be an alphabet.

By $A^{**}$ let us denote the set of all strings from $A^*$ of even length. (This definition may be incorrect but it was given to me in the question)

Show that $$(AA)^{*} = A^{**}$$

My Answer:

I believe I need to show two cases, not sure if I proved the cases exactly correct.

1. $(AA)^{*} \subseteq A^{**}$
2. $A^{**} \subseteq (AA)^{*}$

case 1: Suppose $w \in (AA)^{*}$ then by definition of Kleene star $w$ will contain $0$ or more strings of $AA$ which means $w$ can be a string from $A^*$ since $A^*$ just repeats the string with a longer length and concatenation with two strings from $AA$ is the same as a string repeated with longer length so

$$w \in A^{**} \implies (AA)^{*} \subseteq A^{**}$$

case 2: Suppose $w \in A^{**}$ then $w$ is a $0$ or more strings from the alphabet $A$ and adding another Kleene star would make more combinations of the strings from $A$ with higher length which is the same as concatenating two strings to equal the same length so

$$w \in (AA)^{*} \implies A^{**} \subseteq (AA)^{*}$$

Answer 1

Much of your trouble with this problem seems to come from the poor choice of notation by the author: $A^{**}$ is not a good way to denote the set of even-length strings. Pre-empting the result we are asked to prove, one might suggest $A^{2*}$.

---

The key to understanding the theorem, as well as where you went wrong in your proposed solution, is to understand what a string of elements of $AA$ looks like.

The way you put it:

concatenating two strings to equal the same length

suggests that you interpret $(AA)^*$ as being $A^*A^*$, i.e. the concatenations of two strings in $A$.

However, let us explicitly expand the definition of Kleene star:

$$(AA)^* = \{w_1 w_2 \ldots w_n: n \ge 0, \forall n: w_n \in AA\}$$

Now ask yourself the following questions:

• Would it be possible to construct e.g. the single-character string $a$ as an element of $(AA)^*$?
• What is the length of $w_1w_2\ldots w_n$?
• What are the elements of $(AA)^*$?