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.

  • $\begingroup$ 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? $\endgroup$ – babou Dec 10 '14 at 17:33
  • $\begingroup$ @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. $\endgroup$ – user76508 Dec 10 '14 at 17:55
  • 6
    $\begingroup$ Hint: think nondeterministic. machine may guess and check. $\endgroup$ – Hendrik Jan Dec 10 '14 at 18:07
  • $\begingroup$ @HendrikJan thanks, I'll try to think that way. $\endgroup$ – 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| \}. $$

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ This grammar derives $10$@, which isn't in the language: $S\Rightarrow 1X\rightarrow 10X\Rightarrow 10$@. $\endgroup$ – Rick Decker Dec 12 '14 at 0:40
  • $\begingroup$ @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). $\endgroup$ – Ran G. Dec 12 '14 at 2:45
  • $\begingroup$ 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. $\endgroup$ – Dezi Dec 13 '14 at 10:50

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.