# Is the set of strings $0^{2k}10^{2k}10^{k}$ for $k \geq 0$ context-free?

I am able to solve $0^{k}10^{k}10^{j}$ where $k < j$. and I was able to see that this is also a concatenation of two strings. How to do it for $0^{2k}10^{2k}10^{k}$ for $k \ge 0$?

• Unless I'm missing something, neither of your examples is a CFL. – Rick Decker Nov 18 '16 at 18:03
• You are right, I neglected to mention it was a unrestricted grammar. – Steven Nov 19 '16 at 3:37
• If you neglected to mention something, please edit the question to correct it. We want questions to be self-contained. Comments exist to help you improve the question; people shouldn't have to read the comments to understand what you are asking. – D.W. Nov 19 '16 at 16:43
• The title of your question doesn't make any sense and bears little relation to the body. Please state the question clearly! – reinierpost Nov 19 '16 at 23:06

There is no context free grammar that can accept those two sets. You can show that using the pumping lemma for CFLs.

Suppose $L = \{x \in \{0,1\}^* \mid x = 0^{2k}10^{2k}10^{k}, k \geq 0 \}$
Let $n$ be the pumping lemma constant.
I can choose $z = 0^{2n}10^{2n}10^{n}$. Clearly $|z| \geq n$. Now let $z = uvwxy$ be any decomposition of $z$ such that $|vwx| \leq n$ and $|vx| > 0$.

Case 1: Either $v$ or $x$ contains at least one $1$. Then the string $z^\prime = uv^0wx^0y = uwy$ contains strictly less that two $1$s, so $z^\prime \notin L$.

Case 2: Both $v$ and $x$ entirely consist of $0$s. Note that since $|vwx| \leq n$, therefore $vwx$ can cover at most 2 'parts' (contiguous substring of $0$s) of the original string $z$. So, we again choose the string $z^\prime = uv^0wx^0y = uwy$. The third 'part' of the string which is not covered by $vwx$ will then violate the condition and $z^\prime \neq 0^{2m}10^{2m}10^m$. So, $z^\prime \notin L$.

So, $L$ is not a context-free language. A similar proof can be given for $0^{k}10^{k}10^{2k}$. I have no idea how you were able to 'solve' this one!

## EDIT

The question was edited from context-free grammars to context sensitive grammars. The language $L = \{x \in \{0,1\}^* \mid x = 0^{2k}10^{2k}10^{k}, k \geq 0 \}$ can indeed be generated from a context-sensitive grammar.

\begin{align} S^\prime &\rightarrow WS \\ S &\rightarrow LRS0 \mid 1 \\ RL &\rightarrow RM \\ RM &\rightarrow LM \\ LM &\rightarrow LR \\ WL &\rightarrow WV \\ WV &\rightarrow LV \\ LV &\rightarrow LW \\ W &\rightarrow 1 \\ L1 &\rightarrow 001 \\ L0 &\rightarrow 000 \\ 1R &\rightarrow 100 \\ 0R &\rightarrow 000 \end{align}

• Maybe my terminiology is wrong but for this one, $0^{k}10^{k}10^{2k}$ all I did was the following. S -> AB A -> 0RA2 | 012| empty R0 -> 0R R1 -> 11 B -> 2B | 2 Maybe I should of mentioned it was unrestricted because this is the solution to this question. But now that I said this, I realize my error I made and will edit it... However the $0^{2k}10^{2k}10^{k}$ is an accurate problem – Steven Nov 19 '16 at 3:32
• The problem I solved should read $0^{i}10^{i}10^{j}$ where i < j. My edit time ran out but just needed to make it clear. I see how pumping lemma proves this wrong, but does it being unrestricted change this solution at all? – Steven Nov 19 '16 at 3:39
• I'm not entirely sure what you mean by unrestricted. If you're talking about unrestricted grammars, then yes it can be generated by an unrestricted grammar. – skankhunt42 Nov 19 '16 at 5:09
• Yup! Thanks, sorry :/ I didn't know unrestricted was used for other things, but yeah unrestricted grammars – Steven Nov 19 '16 at 15:57
• Your context-sensitive grammar is not context-sensitive (which allows to replace one non terminal without modifying its context). It is a non-contracting one. There is an algorithm to transform non-contracting grammar into context-sensitive one so there is no difference in expressive power but context-sensitive grammar tends to have even more rules. – AProgrammer Nov 20 '16 at 7:07