# Is there a Context-free grammar for this language?

Is there a Context-free grammar for the following language:

$L=\{ x\#1^m|x \in \{0,1\}^* \text{ and the$m^{\text{th}}$char in$x$is 1} \}$

If so what is it? Because i couldn't find any. I also tried to prove there isn't (by the Pumping lemma for context-free languages), but it's given that a Context-free grammar does exist and I found an error in my "proof".

So what would be the grammar?

Here's the big picture of my proof:

Let's choose $m=n_0$ and take the word $w=0^{n_0}1\#1^{n_0+1}$ (so that $x$ is what's on the left side of $\#$) .

According to the lemma, $w$ can be written as $uvxyz$ and some conditions hold...

$|vxy| \leq n_0$

therefor, $vxy$ include only zeros ($0$'s).

Now let's choose k=2 and pump it up:

we get: $w_2=uv^2xy^2z$

which means, the number of $0$'s is now:

$n_0 + |v| + |y| \geq n_0 + 1$

(since $|vy| \geq 1$) .

Hence, the $m$th number (the $n_0$th in our case) is not $1$. It's actually $0$.

Hence, $w_2$ doesn't belong to $L$. Contradiction.

Hence, $L$ isn't Context-free.

I think i know where's my mistake in the proof:

$vxy$ isn't necessarily only $0$'s. It could have the last $n_0-1$ zero's and a $1$.

• possible duplicate of How to prove that a language is context-free?
– D.W.
Apr 26, 2014 at 22:05
• Please put more care and effort into your question. There is no point in including a "proof" that you know to be incorrect. Don't write some long thing that is wrong and then just add "edit: everything above is wrong" at the end of your post when you discover it is wrong. Instead, edit the post to make it well-crafted and stands on its own. Delete all the incorrect stuff. Take pride in your question. Show us what you've tried, and what you think: do you think it is context-free? If yes, what have you tried to try to find a context-free grammar or pushdown automaton?
– D.W.
Apr 26, 2014 at 22:07

Here is a PDA for this language. While reading $x$, the whole of $x$ is pushed onto the stack. After encountering $\#$, the PDA pops some non-deterministic amount of symbols, then verifies that the top symbol is $1$, and pops $m$ symbols. It acceptes if the stack is empty.
Variant: instead of popping a part of $x$, while reading $x$ the PDA non-deterministically stops pushing symbols into the stack; it only does so after reading a $1$.
As for a CFG for this language, here is the idea: \begin{align*} &S \to \Sigma^{m-1} 1 T 1^m \\ &T \to \Sigma^* \# \end{align*}