1
$\begingroup$

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

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

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ exactly this was my confusion, do you think question is ambiguous? $\endgroup$
    – Mk Utkarsh
    Oct 18, 2018 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – rici
    Oct 18, 2018 at 18:40
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ but the notation mentioned in question should not be used? $\endgroup$
    – Mk Utkarsh
    Oct 18, 2018 at 9:49
  • $\begingroup$ No, it is not clear at all. $\endgroup$
    – J.-E. Pin
    Oct 18, 2018 at 9:54
  • $\begingroup$ Ok thanks, this was asked in online tests which are mocks for national level exam for computer science graduates in my country. $\endgroup$
    – Mk Utkarsh
    Oct 18, 2018 at 9:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.