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

Question

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!!!

Answer 1

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)$.

Answer 2

) !

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.

Answer 3

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)$.