3
$\begingroup$

By stack I mean the language of sequences it represents, say, a stack with data domains $N$ (natural number) is: $\{ \mbox{push(0)}, \mbox{push(1)}, \mbox{push(0).push(1)}, ..., \mbox{push(0).pop(0)}, ...\}$.

This language is not against Pump lemma of CFL, right ? But I read from some materials that this language is NOT context-free. So why is that ?

$\endgroup$
  • 1
    $\begingroup$ Where did you read that? What is the language, exactly? $\endgroup$ – Raphael Jul 17 '16 at 14:34
  • $\begingroup$ @Raphael, The language is basically an infinite set of all valid sequences that can be generated from a Stack specification (i.e., LIFO). That is all the valid sequences composed of 'Pushs' and 'Pops', e.g., $\mbox{Push(1) Push(2) Pop(2) Pop(1)}$ is a valid one, while $\mbox{Push(1) Push(2) Pop(1) Pop(2)}$ is not. $\endgroup$ – Gaoang.L Jul 17 '16 at 14:56
6
$\begingroup$

The language is context-free. If we replace $\mathrm{push}(k)$ by $[_k$ and $\mathrm{pop}(k)$ by $]_k$ and delete the dots, then we get exactly all prefixes of a Dyck language with $N$ different types of brackets.

$\endgroup$
  • $\begingroup$ I'm sorry I didn't make clear of the question. Here $N$ is the infinite set of natural numbers, it's not a single number. So in such case, is stack still context-free ? $\endgroup$ – Gaoang.L Jul 18 '16 at 0:47
  • $\begingroup$ @Goon_with_X, I don't think the question is well-defined. In computer science, languages are always subsets of $\Sigma^*$ where $\Sigma$ is finite -- in particular, without loss of generality they are subsets of $\{0,1\}^*$. An infinite alphabet isn't allowed. $\endgroup$ – D.W. Jul 18 '16 at 1:00
  • $\begingroup$ @D.W. But how about we encode the Push, Pop actions with letters from $\Sigma = \{ 0, 1, \#_u, \#_o\}$. Say, use $\#_u 1$ to encode Push(1), use $\#_o1$ to encode Pop(1), $\#_u 10$ to encode Push(2) and $\#_o 10$ to encode Pop(2), etc. Now we have finite alphabet and the language is set of sequences $ L = \{ \#_u 1 \#_o 1, ... \}$ . What conclusion can we get now ? $\endgroup$ – Gaoang.L Jul 18 '16 at 1:54
  • $\begingroup$ @Gaoang.L, That's a different language. Rather than using the comments for an extended discussion, please ask a new question with all of the details worked out, including exactly how you plan to map it to a finite alphabet. (Or, edit the question -- although given that this question has already gotten a good answer, it might be better to ask a new question, rather than invalidating the existing good answer to this question.) Then, show us what you tried. Did you try to find a grammar? What did you try and where did you get stuck? $\endgroup$ – D.W. Jul 18 '16 at 2:17
  • $\begingroup$ @D.W. Good idea and thanks. I will rephrase it and ask a new one. $\endgroup$ – Gaoang.L Jul 18 '16 at 3:02

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.