Shortest string in the intersection of a context-free language and a regular language

Question

For a language $X$, define $ss(X) = \min_{x\in X} |x|$, the length of the shortest string in $X$. For simplicity, we define $ss(\emptyset)=0$. Let $L$ be a context-free language generated by a context-free grammar with $k$ non-terminals. (assuming all context-free grammars are in Chomsky normal form.) Let $R$ be a regular language recognized by an NFA of $n$ states.

What is $ss(L\cap R)$, the length of the shortest string in $L\cap R$?

A naive upper bound is $2^{kn^2}$: find a context-free grammar for $L\cap R$ with $kn^2$ non-terminals.

Motivation: Answer to the above question can lead to a better bound for the following problem.

Let $L$ be a fixed context-free language. Let $\mathcal{R}_n$ to be all the set of all regular languages that can be recognized by an NFA of $n$ states.

Define $f_L(n) = \max_{R\in \mathcal{R}_n} ss(L\cap R)$.

What can we say about the asymptotics of $f_L(n)$?

Using the naive bound, we know $f_L(n) = O(2^{n^2})$.

Answer 1

Thank you very much for posting this question!

I am very enthusiastic about these kinds of research problems. Although I don't have a precise answer, I think that the following will be of help.

The Input Format Matters

A context-free language can be represented as CFG or a PDA. Given that there is a polynomial blow-up in converting from one form to another, we have to be particular about whether $n$ denotes the number of non-terminals from the CFG or the number of states from the PDA.

Similarly, for regular languages, $n$ could denote the length of the regular expression or the number of states from the DFA.

Given that I am personally more comfortable with automata, I will assume that the inputs are given as automata and $n$ will denote the number of states from the larger (or largest) automaton.

A More General Problem

Consider that we are given a PDA $P$ and $k$ DFA's $D_1, D_2, ..., D_k$.

If we are promised that the intersection of these automata is non-empty (that is, $L(P) \cap \bigcap_{i\in [k]} L(D_i)$ is non-empty), then in terms of $n$ and $k$, what is the length of the shortest string in the intersection?

Now, you may ask, in the worst case, how large can this shortest string be? It turns out that there is a constant $c \leq 1$ such that it is always possible to construct a PDA $P$ and DFA's $D_1, D_2, ..., D_k$ so that the shortest string in the intersection has length $2^{n^{c \cdot k}}$.

Note: You will see where $c$ comes from below, but you can probably make it close to $1$. Maybe even $1 - \varepsilon$?

Construction

Disclaimer: This is one possible construction although, it might not be the preferred construction nor is it necessarily optimal. One interesting thing about the construction is that there is only one string in the intersection. The construction is inspired by Cook (1971).

Let a number $n$ be given. Consider an auxiliary pushdown automaton. That is, a state machine with a stack and a bounded work tape.

If we have $k\log(n)$ bits on the work tape, then we can represent any integer from $1$ to $n^k$. You can use this integer to represent a stack height. Now, it is possible to design an auxiliary pushdown automaton with only $k\log(n)$ bits of memory on the tape that counts from $1$ to $2^{n^k}$ and then accepts. It does this by enumerating through every single configuration of the stack of height at most $n^k$ where the current height is always stored in the $k\log(n)$ bits on the work tape.

Please let me know if you need more detail in the preceding description. Otherwise, we will continue our construction.

Now that we have an auxiliary pushdown automaton with only $k\log(n)$ bits on the work tape that runs for $2^{n^k}$ steps before accepting, we can construct $P$ along with $D_1, D_2, ..., D_k$. This construction is inspired by Kozen (1977) and related works.

The idea is to build the PDA and DFA's to read in a string that encodes a computation of the auxiliary pushdown automaton. The computation is accepting if and only if the PDA and DFA's all accept its encoding.

The computation is a sequence of configurations. Each configuration can be encoded by a string so that all of the strings concatenated together make up the computations encoding. Then, the DFA's each are assigned to a $\log(n)$ length chunk of the work tape and verify that the computation for their respective chunk of the work tape carries on correctly. Finally, the PDA pushes, pops, and peeks, as is instructed by the configurations and simultaneously verifies that what is on the stack actually matches what the configuration says is on top of the stack. They accept if both their respective verification is successful and the accepting configuration is reached.

Because the auxiliary pushdown automaton requires a computation of length $2^{n^k}$, the smallest string in the intersection has length at least $2^{n^k}$. And, although it wasn't discussed in detail, the automata can be built to have polynomial in $n$ states. The smaller the degree of the polynomial, the closer that $c$ can be made to 1.

Other Works

• There is a great master's thesis by Thomas Ang on the length of the shortest string in the intersection of regular languages.

• Also, I made a small contribution to a paper with D. Chistikov, W. Czerwinski, P. Hofman, and M. Pilipczuk where we show that the shortest string accepted by a one counter automaton has length at most $c n^2$ for an appropriate constant $c$ (the previously known upper bound was $n^3$).

Dmitry and I have been discussing for a couple years about what the upper bound is for the shortest string accepted by a PDA. You can get a lower bound of $2^n$ and an upper bound of $2^{n^2}$, but can you improve either of these bounds? Even just a small improvement on the upper bound to $2^{\frac{n^2}{\log(n)}}$ would be a breakthrough.

Sorry for such a long reply and for excluding many details. Feel free to shoot me an email if you would like to discuss offline. Thank you and I hope you have a great week!