I will use verifier based definition of NP and coNP (not that with NTM).
Given a word $w$ and a language $L$ consider a graph on $\{1,2,\dots,|w|+1\}$ where $(i,j)$ is an edge iff $w_{i\dots j-1}\in L$. Then, $w\in L^{\ast}$ iff there is a path from $1$ to $|w|+1$.
Is a complexity class closed under Kleene star?
For P the situation is easy; the machine can compute the graph and perform DFS.
For NP, the machine may guess $O(n^2)$ certificates, compute the graph and accept if there is a path. Every edge in the graph corresponds to an infix in the language. If you guess wrongly, you will incorrectly reject, but here the guesses are directed to accept if possible.
For coNP, the machine may also guess $O(n^2)$ certificates, compute the graph and reject if there is a path. Every edge in the graph also corresponds to an infix. If you guess wrongly, you will incorrectly accept, but here the guesses are directed to reject if possible.
Edit to clarify.
If the task was to show NP is closed under Kleene star, you could write ($L \in NP$):
$x \in L^{\ast}$ iff there exists a partition $x=x_1 x_2 \dots x_n$ such that there exist $n$ strings $y_i$, such that each string $y_i$ is a valid certificate for $x_i$.
And this is enough to show that $L^{\ast} \in NP$, since you can guess both the partition and certificates.
However, if you try to pull the same trick with $coNP$, you will get: ($L \in coNP$):
$x \in L^{\ast}$ iff there exists a partition $x=x_1 x_2 \dots x_n$ such that for all $n$ strings $y_i$, each string $y_i$ is a valid certificate for $x_i$.
this is bad, because you've got both existential and universal quantification, so $L^{\ast}$ is not in the form required for coNP.
The idea is to guess certificates for all $n^2$ infixes of the word at once. Some of them will not be valid, but we won't use them.
If $L \in NP$ you can write:
$x \in L^{\ast}$ iff there exists $O(n^2)$ strings, such that there exists a partition $x=x_1 x_2 \dots x_n$ such that each $x_i$ has a valid certificate.
and check existence of partition using the graph.
Given the $n^2$ certificates, the property "there exists a partition $x=x_1 x_2 \dots x_n$, such that..." is testable in polynomial time; you do not need to guess the partition.
For $L \in coNP$ you can pull the same trick now:
$x \in L^{\ast}$ iff for all $O(n^2)$ strings, there exists a partition $x=x_1 x_2 \dots x_n$, where each $x_i$ has a valid certificate.
and since "the exists a partition..." is testable in polynomial time, it shows that $L^{\ast}$ is in $coNP$.
Edit: Another way to think about it.
You've got a word $w$ and want to show that it is not in $K^{\ast}$, where membership in $K$ can be quickly falsified. To do it, you falsify membership of as many infixes of $w$ as you can. If there is no way the remaining infixes could be joined to get the whole $w$, surely $w \notin K^{\ast}$. On the other hand, if you supplied as many falsifications as possible and there is still a way to break $w$ to $w = w_1 w_2 \dots w_n$ where you cannot falsify membership of any $w_i$, then $w \in K^{\ast}$.
Formal proof.
Suppose $K$ is a $\mathsf{coNP}$ language. This means
$x \in K$ iff $\forall y. P(x,y)$
where $y$ is polynomial with respect to $x$ and $P$ is a polynomial time predicate.
I will show that $K^{\ast} \in \mathsf{coNP}$. So I will define a predicate $R$ such that
$x \in K^{\ast}$ iff $\forall y. R(x,y)$
Here is code of $R$. "Accept" means that $R(x,y)=true$ (in this case $y$ is useless) and "reject" means $R(x,y)=false$ (in this case $y$ certifies that $x \notin K^{\ast}$)
def R(x,y):
- Let $n = |x|$.
- Split $y$ into $c_{11} \# c_{12} \# \dots \# c_{1n} \# c_{22} \# c_{23} \# \dots \# c_{nn}$, where $c_{ij}$ are some strings, defined only when $i\leq j$. If $y$ is not of this form, we accept.
- Create a triangular binary matrix $A$ of size $n+1$.
The entry $a_{ij}$ is 0 when $i \geq j$, otherwise it's $P(x[i,j-1], c_{i(j-1)})$
- Use $A$ as a matrix of a graph, and check if there is a path from 1 to $n+1$ (BFS).
- Accept if there is a path, reject if there is no path.
Clearly $R$ is polynomial time computable.
If $x \in K^{\ast}$ then $x=x_1 \dots x_m$, where $x_i \in K$, so $P(x_i,z)$ is always true. In this case there is a path in the graph for any $y$, so $\forall y. R(x,y)$.
If $x \notin K^{\ast}$ then for any $(i,j)$ such that $x[i,j] \notin K$ we define $c_{ij}$ such that $\neg P(x[i,j], c_{ij})$, and $c_{ij}=\epsilon$ otherwise. Let $y$ be a suitable concatenation of $c_{ij}$.
I claim for such defined $y$ the graph has no path from 1 to n+1, and the algorithm rightfully rejects. Namely, such path would give rise to a partition $x = x_1 x_2 \dots x_n$. However, since $x \notin K^{\ast}$, there exists $i$ such that $x_i \notin K$. Suppose $x_i = x[k,l]$. But in this case we supplied $c_{kl}$ such that this edge should not be present in the graph.
Best Answer
Your understanding of $(0+1)^*$ and $(0+1)(0+1)^*$ is correct.
$(0+1)0^*1^*$ is different from both. The regular expression $0^*1^*$ matches any string of the form $0^m1^n$, where $m,n\ge 0$. Thus, it matches every string that does not have a $1$ before a $0$. $(0+1)0^*1^*$ then matches any string that has at least one character, which may be $0$ or $1$, and after that does not have a $1$ that is followed by a $0$.
$(0^*1^*)^*$ is equivalent to $(0+1)^*$: it matches the empty string and any string of the form $$0^{m_1}1^{n_1}0^{m_2}1^{n_2}\ldots0^{m_r}1^{n_r}\;,$$ where the numbers $m_1,\ldots,m_r$ and $n_1,\ldots,n_r$ are non-negative integers, and it’s not hard to see that that covers every possible string of $0$s and $1$s. Thus, $(0+1)(0^*1^*)^*$ is equivalent to $(0+1)(0+1)^*$.