# How to prove that sequences of stack operations are not context-free

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 ?

• Where did you read that? What is the language, exactly? – Raphael Jul 17 '16 at 14:34
• @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. – Gaoang.L Jul 17 '16 at 14:56

## 1 Answer

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.

• 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 ? – Gaoang.L Jul 18 '16 at 0:47
• @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. – D.W. Jul 18 '16 at 1:00
• @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 ? – Gaoang.L Jul 18 '16 at 1:54
• @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? – D.W. Jul 18 '16 at 2:17
• @D.W. Good idea and thanks. I will rephrase it and ask a new one. – Gaoang.L Jul 18 '16 at 3:02