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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .