3
$\begingroup$

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.

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

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ This grammar derives $10$@, which isn't in the language: $S\Rightarrow 1X\rightarrow 10X\Rightarrow 10$@. $\endgroup$ Dec 12, 2014 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, 2014 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, 2014 at 10:50
0
$\begingroup$

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}

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.