5
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Raphael Jan 27 '15 at 11:19
  • $\begingroup$ @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$.". $\endgroup$ – R B Jan 27 '15 at 11:30
  • $\begingroup$ @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)$. $\endgroup$ – R B Jan 27 '15 at 11:36
2
$\begingroup$

) !

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fatemeh Ahmadi Feb 1 '15 at 19:42
  • $\begingroup$ 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) $\endgroup$ – Doralisa Feb 2 '15 at 5:02
1
$\begingroup$

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

$\endgroup$

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.