In an example question sheet for my exams our professor included “Know to explain why for non CF languages 1 stack is not enough.”
We haven’t delved into CS and reclusively enumerable languages much and I can’t find the answer to this in my book either. I understand how PDAs work for CF languages though and I have a few info on LBAs, but I still don’t grasp why non CF need more than one stack.
As you probably know a language like $\{a^nb^n|n\in \mathbb{N}\}$ is context-free since we can first save the number of all $a$ we read using some symbols (for example A) in the stack and then check that the $b$'s number ( denote it by $n_b$) is equal to $a$'s number or not, by removing all $A$ symbols.
Now, try to look at what makes a language like $\{a^nb^nc^n| n\in \mathbb{N}\}$ to not belong to the context-free class. By having only one stack we are not able to check the equality of three numbers (i.e. $n_a=n_b, n_a= n_c, n_b=n_c$) at a same time. In the other words, if we want to use what data we have saved, we lose it in a way we can not have the data as before.
So we need more than one stack to overcome the limitation of storing data.
By the way, the automaton equipped with two stacks is as powerful as a Turing machine! (That is the class of languages they decide is equal).
