0
$\begingroup$

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

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

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$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your reply! but, notice that I asked if L is context free grammar and not regular. $\endgroup$ – yong May 14 at 13:04
  • $\begingroup$ Sorry, I fixed it. $\endgroup$ – Steven May 14 at 17:07
  • $\begingroup$ Thank you very much :) $\endgroup$ – yong May 15 at 13:21
  • $\begingroup$ 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 $\endgroup$ – yong May 23 at 10:16
  • 1
    $\begingroup$ 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$. $\endgroup$ – Steven May 23 at 10:24
0
$\begingroup$

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...
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much :) $\endgroup$ – yong May 15 at 13:22

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.