# Decide if this language is context free

I got this question for homework:

Decide if this language is context free or not:

$$\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$$.

Intuitively I think it's not context-free because a $$PDA$$ can't remember the places of all the $$1$$'s in $$x$$.

I tried using the pumping lemma but couldn't find the right example to show the language is not context-free.

I'd be grateful for any lead.

• Are you sure that $x@1^m$ is supposed to be the language of strings of 0 and 1 such that the $m^{th}$ symbol is a one? And $m$ is the same for the whole language? - - - How many places can a PDA remember? - - - is this an exercise for a course on CF languages and PDA? Dec 10, 2014 at 17:33
• @babou I'm sure that is the language (of course there is a '@' sign in between. m is not the same for the whole language. for example, if x=0110101, the PDA will accept words in-which m is 2,3,5 or 7. m=1,4 and 6 will not be accepted in the PDA. Dec 10, 2014 at 17:55
• Hint: think nondeterministic. machine may guess and check. Dec 10, 2014 at 18:07
• @HendrikJan thanks, I'll try to think that way. Dec 10, 2014 at 18:46

Hint: Following up on Hendrik Jan's hint, here is another way to view this language: $$\{ x1y@1z : x,y \in \{0,1\}^*, z \in \{1\}^*, |x| = |z| \}.$$

I think the context free grammar with these productions and starting symbol S produces your language (assuming words start at index 0):

S -> 0S1
S -> 1S1
S -> 1X
X -> 0X
X -> 1X
X -> @

Explanation: You can produce any words from {0,1}* with index < mand add a 1to the right part of the word. When you reach index m, you switch to X and continue the word from {0,1}*. You can end the word by producing an @.

• This grammar derives $10$@, which isn't in the language: $S\Rightarrow 1X\rightarrow 10X\Rightarrow 10$@. Dec 12, 2014 at 0:40
• @Rick, it's just mis-indexing, if you call the first letter $x_0$ instead of $x_1$ then it works correctly. So this is a strong evidence that the question is CF (proven with a slight change to the above grammar). Dec 12, 2014 at 2:45
• Ran is right. As I said: "assumging words start at index 0". If words start at index 1, remove the Production S -> 1X and insert a new production S -> 1X1.
– Dezi
Dec 13, 2014 at 10:50

Let $$L = \{x@1m:x\in\{0,1\}^∗,m\in N,x_m=1\}$$.

A language $$L$$ is context-free when a context-free grammar $$G = \langle\Sigma, N, S, R\rangle$$ such that $$L(G) = L$$ (the language of $$G$$ is the same as $$L$$).

\begin{align} G = \langle\{0, 1\}, \{S, X\}, S, \{&\\ &\qquad X \rightarrow 0X,\\ &\qquad X \rightarrow 1X,\\ &\qquad X \rightarrow \epsilon,\\ &\qquad S \rightarrow 0S1,\\ &\qquad S \rightarrow 1S1,\\ &\qquad S \rightarrow 1X@1 \\ &\}\rangle \end{align}

• I find it hard to spot the difference from Dezi's '14 answer. Sep 4, 2020 at 7:13