# Is this language Regular or non regular

$$(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

• Could you please give a clear formal definition of your language. At the moment, it does not make any sense. Oct 18, 2018 at 8:49
• what's informal about it? It is kleene star of a regular language which is $0^n 1$ where $n \geq 0$ Oct 18, 2018 at 8:53
• What are the $V_k$ in the second wiki definition, after "But again on wiki"? Oct 18, 2018 at 9:22
• Given a set V define $V_0 = {ε}$ (the language consisting only of the empty string), $V_1 = V$ Oct 18, 2018 at 9:27
• What are $V_2$ and so on? is each the concatenation of previous one with $V$? Oct 18, 2018 at 9:44

## 3 Answers

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.

• exactly this was my confusion, do you think question is ambiguous? Oct 18, 2018 at 18:37
• No, I don't. I find the question quite clear. However, it is often the case that some people misunderstand something. I included my reasoning, fwiw.
– rici
Oct 18, 2018 at 18:40

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.

• but the notation mentioned in question should not be used? Oct 18, 2018 at 9:49
• No, it is not clear at all. Oct 18, 2018 at 9:54
• Ok thanks, this was asked in online tests which are mocks for national level exam for computer science graduates in my country. Oct 18, 2018 at 9:57

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.