# Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$.

Obviously, this class is a proper subset of the class of context-free languages. Which languages are in this class, and what (closure) properties does it have?

I have found this class in Harrison's Book: I have searched a lot about iterated counter languages but I can't understand them well. I also I don't know whether this problem is what I am looking for or not.

I think if we have L1 and L2 in this class so we can have their union in this class by adding two lambda- transition.

And if we have a Pda A with logarithmic stack height , if we can construct an equivalent Pda B with the extra property that always clear all its stack symbols except the bottom-of-stack symble after every acceptance so we this class will be closed under Kleene- star

I will be grateful if anyone can explain me whether this class is closed under intersection and complement or not

I am still looking for just one non-regular-language that is in this class!!!

• In case of non-determinism, do all computations satisfy the stack bound, or only accepting ones? – Raphael Jan 27 '15 at 11:20

The class $LOG_{CF}$ is in fact the class of regular languages $R$ (and thus have all of the regular languages closure properties).

$R\subseteq LOG_{CF}$ is trivial, so we'll concern ourselves only with the the other direction.

Let $A$ be some PDA, and let $s(n)$ be the maximal stack size of $A$'s run on a length-$n$ word. First notice that if $s(n)=O(1)$, then $L(A)$ is regular (you can always encode a finite set of stack configurations into a NFA).

We will claim that if $s(n)=\omega(1)$, then $s(n)=\Theta(n)$, thus there can't be any PDA which is guaranteed to use non-constant sub-linear space.

We define Automaton-Sub-Configuration to be a tuple $(q,x)\in Q\times \Gamma^*$ such that currently the automaton is in state $q$, and the top of his stack (the suffix of the stack word), is a word $x\in\Gamma^*$.

Now if $s(n)=\omega(1)$, there has to be some automaton sub-configuration, $(q',x')$, for the such that:

$(q',x')$ can be reached unbounded number of times, and on every time it is reached, the stack size grows by at least one symbol.

Let $w_0\in \Sigma^*$ be a word such that the automaton would reach $(q',x')$, and let $w_1$ be a word such that when reading $w_1$ out of $(q',x')$, the automaton ends at $(q',x')$ with at least one additional symbol in the stack.

Finally, consider the word $w=w_0\cdot w_1^k$. Notice that the automaton stack size after reading $w$ is (at least) $k$, while $|w|=|w_0|+k|w_1|$, hence the stack size could be linear in the length of the word.

The conclusion is that for any PDA $A$, $s(n)=O(1)$ or $s(n)=\Theta(n)$.

• How do we know that this is the only computation that accepts $w = w_0 w_1^k$? There may be others that use the stack better. We have a non-deterministic PDA, after all. (I assume that non-accepting runs on words in the accepted language don't have to fulfill the bound.) – Raphael Jan 27 '15 at 11:19
• @Raphael - I assumed $LOG_{CF}$ is the set of languages whose PDAs may not use more than $\log n$ stack size on any run, no matter if the word is in their language or not. That was the OP's definition: "Let $LOG_{CF}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq\log n$ cells of its stack for each input of length $n$.". – R B Jan 27 '15 at 11:30
• @Raphael - also, I think the claim still holds even under your definition (there has to be some repeating sub-configuration for accepted word) - it just takes adjustment of the definition of $s(n)$. – R B Jan 27 '15 at 11:36

) !

My answer result exactly is the same as above but I hope this answer be useful for the others and if there is something wrong with it, I understand it and correct it and learn it .

It wasn’t obvious for me that this class is equal to context free so after proving some of its properties I tried to find a language in this class then I realized that I can't find any non-regular language and this led me to following:

$LOG_{CF}= R$ , which $R$ means class of regular languages.

Suppose that $\Sigma = \{0,1\}$

We claim that $LOG_{CF}= R$. it follows $LOG_{CF} - R= \emptyset$. Proof by contradiction: let $L\in LOG_{CF}$. So there is a PDA like P that $L(P)=L$ and for all $w \in L$ P uses its stack's cells at most $log|w|.$ We know that every context free languages that its words contains only one alphabet are regular, so $\forall w \in L$ , $w$ would be an string including 0 and 1. Let $n_0(w)$ and $n_1(w)$ be respectively number of 0s and 1s. Since P at most uses $log|w|$ cells of its stack, $n_0(w)$ and $n_1(w)$ don’t have linear relationship. We can conclude using Parikh theorem that $L$ is not context free! If $L$ is not context free then there is no PDA like P. it means $L \notin LOG_{CF}$ and that is the contradiction.

• you claimed that every language over 0,1 that is in logcf, at most uses log|w| cells of stack, hence the relation of n(0) and n(1) is nonlinear. so it is not cf , hence is not in logcf. From what you have said one can conclude that there is no language in logcf over two characters, so you confine logcf to the one-character-languages. – Fatemeh Ahmadi Feb 1 '15 at 19:42
• I didn't conclude that there is no language in logcf over two characters. I conclude that there is is no non-regular over two character is in logcf. I mean all languages over two alphabet in this class are regular. regular languages use finite cells of stack(and even we can make PDA for them without using its stack) – Doralisa Feb 2 '15 at 5:02

I'm afraid the accepted answer which claims that $LOG_{CF}=REG$ is not correct.

In section 6 of this reference, Klaus Reinhardt gives a simple example of non-regular language that can be accepted by pushdown automata using $\sqrt{n}$ stack space.

This language is defined as the set of finite non-prefixes of the following infinite word:

$baba^2ba^3ba^4ba^5b...$

Additionally, in the same paper it is shown that for each function f(n) between $\log n$ and $n$, there is a context free language that can be accepted in pushdown space $f(n)$, but not in pushdown space $o(f(n))$.

Note that the paper is written in terms of height of parse-trees for context free grammars. But height $f(n)$ is equivalent to pushdown space $f(n)$.