difference between A* and 2^A*

Question

let A be any input alphabet then what is the difference between

A* (kleen closure of A) and 2^A* ?

Answer 1

$A^*$ is the set of finite strings of elements of $A$.

$2^{A^*}$ is the set of all subsets of $A^*$, that is, the set of all languages. This is vastly larger. For example, the following are elements of $2^{A^*}$:

• The set of all strings of length $1$.

• The set of all strings not containing some fixed element $a\in A$.

• The set of all strings in which every element of $A$ occurs the same number of times.

• Etc.

Answer 2

We can show that $A^*\cong\mathbb N$ through a Gödel encoding of the indices of the letters of the alphabet. From this it follows that $P(A^*) \cong P(\mathbb N)$.

So, for any alphabet $A$, $A^*$ is countable, while $2^{A^*}$ is uncountable.

You will have to be more specific if you want a more specific answer.

---

I'd like to take this time to address something I've seen many textbooks brush over.

Given an alphabet $A$, we let $A^*$ denote the set of all possible strings on the alphabet. Since a string is a finite sequence of letters on the alphabet $A$, then we can define $$A^* = \{\, \alpha\colon n\to A\mid n\in\mathbb N \,\}.$$ That is, $A^*$ is the set of all functions from any natural number $n$ to the alphabet $A$.

Now given an alphabet $A$, a language is defined to be any subset of $A^*$. That is, if $L\subseteq A^*$, then $L\in \mathcal P(A^*)$. Here $L$ is called a language on $A$.

The Kleene star $\bigstar$ is a unary operator on languages, and is defined as follows for any language $L$: $$L^\bigstar = L^0 \cup L^1 \cup L^2 \cup \cdots \,.$$

Since an alphabet is not a language, then $A^\bigstar$ is a meaningless statement, since the Kleene star is only defined on languages. Some might say I am being pedantic, but I believe textbooks should at least mention this detail. Since most regard the letter $a$, and $\langle a\rangle$ (that is the string of length $1$) to be the same, then we might say $A^* = A^\bigstar$, but this is technically not true.

To dothis properly, we define $A_s$ to be the set of the letters of $A$ thought of as strings. That is $A_s = \{\, \langle a \rangle \mid a\in A\,\}$. Clearly $A\cong A_s$. Then it is true that $A^* = (A_s)^\bigstar$.