# 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? – babou Dec 10 '14 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. – user76508 Dec 10 '14 at 17:55
• Hint: think nondeterministic. machine may guess and check. – Hendrik Jan Dec 10 '14 at 18:07
• @HendrikJan thanks, I'll try to think that way. – user76508 Dec 10 '14 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$@. – Rick Decker Dec 12 '14 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). – Ran G. Dec 12 '14 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 '14 at 10:50