Is this language Regular or non regular

Question

$(0^n 1)^* \ \ , n\geq 0 $

According to wiki

If V is a set of strings, then V* is defined as the smallest superset of V that contains the empty string ε and is closed under the string concatenation operation

If V is a set of symbols or characters, then V* is the set of all strings over symbols in V, including the empty string ε.

So this language accepts all strings over $\Sigma^*$ which must be regular. Also regular languages are closed under kleene star.

But again on wiki

$V^* = \bigcup\limits_{i\geq 0}^{} V_i = {\epsilon} \ \cup \ V_1 \ \cup V_2 \ \cup \ V_3 \ \cup .....$

Now according to this definition strings such as $01001$ cannot be a part of given language so $0$'s prior of every 1 are compared within a string, so this can't be regular.

But according to the former definition $01001$ is a part of language because it can be formed with symbols $01$ and $001$ both are part of $0^n 1$.

Can someone help me in identifying the class of these types of languages

Answer 1

If I understand correctly (and no, your definition is neither clear nor correct since $\{(0^n1)^* \mid n \geqslant 0\}$ does not make any sense), your language is $\{0^n1 \mid n \geqslant 0\}^*$, which can be rewritten as $(0^*1)^*$, which is indeed a regular language.

Answer 2

My reading of this question (which I think is the natural reading, notwithstanding other possibilities) is that the language being defined is:

$$L = \bigcup\limits_{n\geq 0}^{} (0^n1)^*$$

which is, roughly speaking, the language of all strings in $\{0,1\}^*$ ending in $1$ in which the $1$s are evenly-spaced. (In other words, there is an implicit "union over all $n$".) That language is not regular, which is easy to prove with the pumping lemma. (Take the string $(0^{p+1}1)^5$.)

I don't see any natural interpretation of $(0^n1)^*$ in which the $n$ is not fixed. It seems unlikely that the intent was $\left(\bigcup\limits_{n\geq 0}0^n1\right)^*$, since that would naturally be written $(0^*1)^*$, not $(0^n1)^*$. That language is regular, as you know, but I don't think it is relevant to this question.

Answer 3

I take it that you mean $L = \bigcup_{n \ge 0} \mathcal{L}((1^n 0)^*)$, i.e., arbitary repeats of $1^n 0$ for each $n$. If you try to dream up an DFA to recognize this, you'll see it would need to record $n$ somehow to check the others, and as $n$ is not limited, that won't work. So suspect it isn't regular.

For a proof, use the pumping lemma. Assume your language $L$ is regular, then there is a constant $N$ such that for each word $\sigma \in L$ such that $\lvert \sigma \rvert \ge N$ it can be written $\sigma = \alpha \beta \gamma$ such that $\lvert \alpha \beta \rvert \le N$ with $\beta \ne \epsilon$ such that for all $k \ge 0$ it is $\alpha \beta^k \gamma \in L$. Pick $\sigma = 1^N 0 1^N 0 \in L$, $\lvert \sigma \rvert = 2 N + 2 \ge N$. But then $\beta$ is formed just by $1$ (say $\lvert \beta \rvert = u$, $u > 0$), if you pick $k = 2$ it is $\alpha \beta^2 \gamma = 1^{N + u} 0 1^N 0 \notin L$. This contradiction shows $L$ is not regular.