7
$\begingroup$

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic pushdown automaton with $n$ states (holding alphabet size constant)?

I found an example where the shortest word is $\Omega(n^2)$ and suspect that this bound is tight, but have been unable to prove it. Everything I found online talking about shortest words is talking about finite or two-way automata only, not pushdown automata.

As an example, choose two large prime numbers $p$ and $q$, and two input symbols $a$ and $b$. Create an automaton with a cycle of length $p$ that reads an $a$ and pushes onto the stack, with a transition to a cycle of length $q$ that reads a $b$ and pops from the stack.

By placing the initial and accept states at appropriate places on the first and second cycle, you force the automaton to go through the first cycle $q-1$ times and the second cycle $p-1$ times, so that the maximum stack length is the same modulo $p$ and $q$, and thus the shortest word has length $\Omega(pq)$. Since the automaton has $p+q$ states, this means the shortest word is $\Omega(n^2)$.

$\endgroup$
  • 3
    $\begingroup$ For "general" (not necessarily deterministic) PDAs, you can build examples where the shortest word is in $2^{\Omega(n)}$. For a given CFG of size $n$, there is always a PDA of size at most $O(n^3)$ accepting the language generated by the CFG. And we know that the length of shortest word generated by a CFG can be exponential in its size. So you get a trivial example in $\Omega(2^{\Omega(\sqrt[3]{n})})$. $\endgroup$ – Lamine Nov 23 '19 at 15:32
  • $\begingroup$ Thanks. I think the construction works for deterministic PDAs too, so the answer is exponential. It does however require a stack alphabet of size O(n), as far as I can tell. I think with a fixed stack alphabet, it becomes polynomial again. $\endgroup$ – Antimony Nov 23 '19 at 15:56
6
$\begingroup$

The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman). And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols. For example, a classic construction turns a grammar like

$S \rightarrow X_1 X_1$

$X_1 \rightarrow X_2 X_2$

$X_2 \rightarrow X_3 X_3$

...

$X_{n-1} \rightarrow X_n X_n$

$X_n -> a$

into a 3-state machine accepting the language $\{\,a^{2^n}\,\}$ by final state, no matter how many variables there are, or into a 1-state machine accepting by empty stack. This gives a classic example of how the shortest string can be exponential in the description size of the PDA.

$\endgroup$
  • $\begingroup$ Could you please explain this "classic construction"? I can't find anything about it online. $\endgroup$ – Antimony Nov 29 '19 at 0:52
  • 1
    $\begingroup$ Naturally, most of the classic proofs are not online (at least not the original version). I found that the proof of Theorem 5.4.1 in M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978 (the "pumping lemmings book") contains the construction of a 1-state pda accepting with empty stack. Its stack alphabet is identical to the variables of the grammar. I warmly recommend working through this book - it discusses several descriptional complexity questions like the one you asked. $\endgroup$ – Hermann Gruber Dec 16 '19 at 18:52
  • 2
    $\begingroup$ Ah yes- and Jeffrey's answer refers to nondeterministic PDAs, which was not exactly what you were asking for. $\endgroup$ – Hermann Gruber Dec 16 '19 at 18:59
5
$\begingroup$

(Answer inspired by Lamine's comment)

We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack alphabet of size $k$, we can construct an automaton that accepts a word of length $O(n^{k+c})$.

The basic idea is to just make the stack as large as possible, and then accept a unary word of that length. If we have stack symbols $a_1, a_2, \dots, a_k$, we can construct the automaton as follows:

If the top symbol is $a_k$, pop it and transition to a sequence of $n/k$ states that each accept a character of input. Otherwise, if the top of the stack is $a_i$, pop it and transition to a sequence of $n/k$ states which pushes $n/k$ copies of $a_{i+1}$ onto the stack. This results in accepting a single word of length $O((n/k)^k)$.

Edit: It turns out that you can simulate $k$ stack symbols using only $2$ stack symbols, by using a $\log(k)$ depth tree of states to "pop" symbols from the stack and a sequence of $\log(k)$ sequence of states to "push" symbols onto the stack. This means that with only two stack symbols, you can still have a minimum word that is nearly exponential in $n$.

$\endgroup$
  • 1
    $\begingroup$ I don't understand why the stack alphabet should be in $\Omega(N)$. The conversion between a CFG and a PDA preserves the input alphabet size, which is the same as the stack alphabet. See the conversion algorithm in "Introduction to automata theory, languages and computation" by Hopcroft et al. $\endgroup$ – Lamine Nov 24 '19 at 13:29
  • 2
    $\begingroup$ Moreover, you can convert your solution giving a word of length $\Omega(n/k)^k$ into a solution giving a word of length $\Omega(\sqrt{n}3^{\Omega(\sqrt{n})})$ by "emulating" each terminal $a_i$ $(1\leq i\leq k)$ by a subword $ab^i a$ and slightly transforming the PDA. You get a solution with superpolynomial length and only two protocols. $\endgroup$ – Lamine Nov 24 '19 at 13:37
  • $\begingroup$ However, one has to check if the new construction is still deterministic. $\endgroup$ – Lamine Nov 24 '19 at 13:39
  • 1
    $\begingroup$ @Lamine I just realized that you don't even need the unary encoding you proposed. You can just use a binary encoding to simulate a stack alphabet of size $k$ using $log(k)$ symbols from a 2-symbol alphabet with a corresponding $log(k)$ blowup in state size when writing to the stack and $k$ blowup when reading from the stack. This results in a nearly exponential solution. $\endgroup$ – Antimony Dec 20 '19 at 20:24

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.