$L = (0^i 1)^n$ where i=1,2,3,4...n and n>=0

For eg :- 00010001 doesn't belong to the language as n=2 but i=3 at the beginning.

001001001 belongs to L as n=3 and i=2 in all cases.

I know the above language is not regular for sure as value of 'i' depends on value of 'n' and it requires comparison. So DFA not possible.

Now I am not sure to which class of language does the above language belong because to check number of zeroes or 'i', we need value of 'n' which can be found out only after reading the entire string.

Can someone please help?

  • $\begingroup$ To check whether a language is context-free or not, try simultaneously to construct a context-free grammar for it, and to use the pumping lemma or closure properties to prove that it isn't. $\endgroup$ – Yuval Filmus Dec 9 '17 at 14:58
  • $\begingroup$ It's not super clear what $L$ is – try harder explaining it. $\endgroup$ – Yuval Filmus Dec 9 '17 at 14:58
  • $\begingroup$ For example, it's not clear whether it has to be the same number of zeroes $i$ in all $n$ copies. $\endgroup$ – Yuval Filmus Dec 9 '17 at 15:42
  • $\begingroup$ You should update your post accordingly. The notation $w^n$ means $n$ concatenated copies of $w$. $\endgroup$ – Yuval Filmus Dec 9 '17 at 16:38
  • $\begingroup$ @YuvalFilmus Oh, yes, sorry for that. Yes, number of i's should be same in all concatenated copies. I don't know what I was thinking. $\endgroup$ – Zephyr Dec 9 '17 at 16:42

Suppose there exists a CFG whose language is $L$, and let $k$ be the pumping length. Consider the string $(0^k1)^k \in L$. Then, by pumping lemma, there exists a decomposition $(0^k1)^k = uvwxy$ where $|vwx| \leq k$, $vx \neq \varepsilon$, and for each $i \geq 0$, $uv^iwx^iy \in L$. Since $|vx| \leq |vwx| \leq k$, there are four types of values of $vx$: either $vx \in 0^+$, $vx \in 0^+1$, $vx \in 10^+$, or $vx \in 0^+10^+$. Try showing that in each of these cases, pumping $vx$ gives a string not in $L$, thus giving a contradiction and demonstrating that $L$ is not context-free.

  • $\begingroup$ So is the above language CSL? $\endgroup$ – Zephyr Dec 10 '17 at 15:35
  • $\begingroup$ That's not something I'm familiar with, but at a glance, I think it is likely, since deciding whether a string is in $L$ is straightforward. Feel free to ask it as a separate question. $\endgroup$ – theyaoster Dec 11 '17 at 7:12
  • $\begingroup$ @Brian Yao, Suppose I take a string 001 001 which belongs to the language. I can take $v$ = 001 and $x$=001. Now if I pump $v$ and $x$ for $i$ times, all of those strings belong to the language . So why is it not CFL ? $\endgroup$ – Rajesh R Jan 18 '18 at 15:08
  • $\begingroup$ Similarly for other strings (infact all) like 0001 0001 0001, we can have $u$ = $\epsilon$, $v$ = 0001, $w$=$\epsilon$, $x$ = 0001 $y$=$\epsilon$. We can again pump all strings belonging to L with the above $v$ and $x$. $\endgroup$ – Rajesh R Jan 18 '18 at 15:13
  • 1
    $\begingroup$ While those strings can be pumped, the one that I provided cannot. Showing this one string cannot be pumped is sufficient to prove that the language is not a CFL. The argument uses the pumping length $k$; since $|vwx| \leq k$, it must be the case that $|v| \leq k$ and $|x| \leq k$. Thus, since $|0^k1| = k + 1 > k$, $v$ and $x$ cannot be equal to $0^k1$. $\endgroup$ – theyaoster Jan 18 '18 at 18:51

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.