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

  • 4
    $\begingroup$ Unless I'm missing something, neither of your examples is a CFL. $\endgroup$ – Rick Decker Nov 18 '16 at 18:03
  • $\begingroup$ You are right, I neglected to mention it was a unrestricted grammar. $\endgroup$ – Steven Nov 19 '16 at 3:37
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Nov 19 '16 at 16:43
  • 1
    $\begingroup$ Steven please delete your obsolete comments and check whether edit caught everything crucial. In the future please make sure that your question is self-contained and clear. Please consider accepting skankhunt42's answer as he already answered two questions. $\endgroup$ – Evil Nov 19 '16 at 22:56
  • 1
    $\begingroup$ The title of your question doesn't make any sense and bears little relation to the body. Please state the question clearly! $\endgroup$ – 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!


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

  • $\begingroup$ 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 $\endgroup$ – Steven Nov 19 '16 at 3:32
  • $\begingroup$ 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? $\endgroup$ – Steven Nov 19 '16 at 3:39
  • $\begingroup$ 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. $\endgroup$ – skankhunt42 Nov 19 '16 at 5:09
  • $\begingroup$ Yup! Thanks, sorry :/ I didn't know unrestricted was used for other things, but yeah unrestricted grammars $\endgroup$ – Steven Nov 19 '16 at 15:57
  • $\begingroup$ 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. $\endgroup$ – AProgrammer Nov 20 '16 at 7:07

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.