Is the following language is a context free grammar language?

$\Sigma=\{0,1,\#\} \newline L = \{x\#y : x,y\in \{0,1\}^* \land \text{x is a substring of y} \}$

The question is to determine whether L is a context free grammar language, what do you think?

• Probably best to intersect $L$ with the regular language $0^*1^* \# 0^*1^*$ first. – Hendrik Jan May 14 at 17:25

2 Answers

Consider the word $$w = 0^n1^n0^n \# 0^n1^n0^n \in L$$ for a sufficiently large value of $$n$$.

By the pumping lemma for context-free languages, we know that if $$L$$ is context-free then there are$$a,b,c,d,e = \Sigma^*$$, with $$|bcd| < n$$ and $$|bd|>1$$ such that $$w=abcde$$ and, for every $$i \ge 0$$, $$a b^i c d^i e\in L$$.

Notice that neither $$b$$ nor $$d$$ can contain $$\#$$, as otherwise setting $$i=0$$ would show that $$a c e \not\in L$$.

If $$c$$ contains $$\#$$, then $$b,d \in 0^*$$ and $$a b^i c d^i e$$ is a word of the form $$0^n 1^n 0^{x + i|b|}\#0^{y+i|d|} 1^n0^n$$ with $$x+|b|=n$$ and $$y+|d|=n$$. If $$|b|>0$$ you can make the first part of the word (before $$\#$$) end with more than $$n$$ zeros by picking $$i=2$$, resulting in a contradiction. Otherwise $$|d|>0$$ and you can make the second part of the word (after $$\#$$) start with less than $$n$$ zeros by setting $$i=0$$.

If $$c$$ does not contain $$\#$$ then $$b$$ and $$c$$ either both precede or both follow the unique occurrence of $$\#$$ in $$w$$. If they precede $$\#$$, pick $$i=2$$. If they follow $$\#$$, pick $$i=0$$. In this way the first part of the word becomes longer than the second (and hence not in $$L$$).

• Thank you for your reply! but, notice that I asked if L is context free grammar and not regular. – yong May 14 at 13:04
• Sorry, I fixed it. – Steven May 14 at 17:07
• Thank you very much :) – yong May 15 at 13:21
• what if x = y and |b| = |d|? Like in the case that c is exactly equals to #. It seems in that case that picking i = 2 won't work – yong May 23 at 10:16
• If $x=y$ (which is the case in the words we are considering) and $|b|=|d|$ then both $b$ and $d$ are non-empty words containing only $0$s. $b$ is in the last group of $0$s of $x$ and $d$ is in the first group of $0$s of $y$. You can either choose $i=2$ (to get more trailing $0$s before the $\#$ character than at the end of the pumped word) or $i=0$ (to get fewer $0$s immediately after the $\#$ character than at the beginning of the pumped word). In any case the pumped word is not in $L$. This seems to be correctly handled in the first case of my answer as it satisfies both $|b|>0$ and $|d|>0$. – Steven May 23 at 10:24

This is not a CFL. We can prove this using pumping lemma for CFL.

We prove it as follows: Consider the string $$s = 0^n1^n0^n\#0^n1^n0^n \in L$$. By pumping lemma, for a significantly large $$n$$, we can split the string in five parts: $$u,v,w,x,y$$ such that $$s = uvwxy$$, $$|vx| > 0$$, and $$uv^mwx^my \in L$$ for all $$m$$.

Basically, you have to find out two parts of the string $$s$$ (at least one is non-empty), such that no matter how many times you pump it, the pumped string has to be in $$L$$.

It is not hard to see that no splitting satisfies the pumping lemma:

• If both $$v$$ and $$x$$ are on left side of #, then the pumped string won't stay substring of the string on right side of #.
• Work out other cases...
• Thank you very much :) – yong May 15 at 13:22