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

  • $\begingroup$ possible duplicate of How to prove that a language is context-free? $\endgroup$ – D.W. Apr 26 '14 at 22:05
  • 2
    $\begingroup$ 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? $\endgroup$ – D.W. Apr 26 '14 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*} $$

I'll let you construct an actual grammar based on this idea.


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.